[알고리즘] 힙 (Heap)

이전글 : )

[알고리즘] 큐 (Queue)

 

---

 

 힙 heap 

힙이란 우선순위 큐를 구현하기 위한 방법 중 하나로 완전 이진트리구조의 자료구조입니다. (우선순위 큐를 구현하는 방법 중 가장 효율적)

힙 내부의 값들은 중복이 허용된 상태로 정렬되며 최소 또는 쇠대 값을 빠르게 찾아내도록 만들어진 자료구조입니다.

느슨한 정렬상태(반정렬 상태)를 유지합니다.

느슨한 정렬상태의 의미는 부모 노드의 키 값이 자식 노드의 카 값보다 항상 큰(작은) 이진트리를 의미합니다.

https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm

 

 종류 

• 최대 힙 max heap
  부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 같은 완전 이진 트리입니다.
  가장 큰 값이 루트 노드에 있습니다.
  Key(parent) ≥ Key(child)
  
• 최소 힙 min heap
  부모 노드의 키 값이 자식 노드의 카 값보다 항상 작거나 같은 완전 이진트리입니다.
  가장 작은 값이 추트 노드에 있습니다.
  Key(parent) ≤ Key(child)

 

 

 구조 

 

힙을 구현하는 방법의 표준적인 자료구조는 배열입니다.

힙의 개발 편의성과 자료의 가독성의 이유로 배열의 인덱스 0은 비우고 인덱스 1부터 사용을 합니다.

 

특정 노드의 인덱스가 i라고 했을 때의 부모 노드와 자식 노드의 인덱스는 아래 계산과 같습니다.

노드 i의 부모 노드 인덱스 : i / 2

노드 i의 왼쪽 자식 노드 인덱스 : i * 2

노드 i의 오른쪽 자식 인덱스 : (i * 2) + 1

최대 힙, 힙의 배열 구조

 

 구현 

 

python을 이용해 최소 힙을 구현해보겠습니다.

최소 힙은 python의 기본 라이브러리인 heapq를 import 해서 힙 구현 없이 사용할 수 있습니다.

이해를 위해 minheap 클래스로 우선순위 큐를 구현해보겠습니다.

 

class MinHeap:

    def __init__(self) :
        self.data = [0]

    def push(self, value) :

        self.data.append(value)

        index = len(self.data) - 1
    
        while index != 1:
            if self. data[index//2] > self.data[index]:
                temp = self.data[index]
                self.data[index] = self.data[index//2]
                self.data[index//2] = temp

                index = index // 2
            else:
                break

값 삽입

힙은 완전 이진트리의 구조를 유지해야 하므로 삽입시 트리의 가장 마지막 노드에 원소를 추가하는 것으로 시작합니다.

삽입 시 부모 노드와 반복적인 비교와 자리 변경을 통해 조건에 만족할 때까지 연산을 한 후 정렬을 마무리합니다.

 

    def pop(self) :

        if len(self.data) == 1 :
            return
        
        self.data[1] = self.data[-1]
        self.data.pop()
        
        index = 1
        
        while True :
            priority = -1
            if len(self.data) -1 < index * 2:
                break
            elif len(self.data) -1 < index * 2 + 1:
                priority = index * 2
            else :
                if self.data[index*2] < self.data[index*2 + 1] :
                    priority = index * 2
                else :
                    priority = index * 2 + 1
            
            if self.data[index] > self.data[priority] : 
                temp = self.data[index]
                self.data[index] = self.data[priority]
                self.data[priority] = temp
                
                index = priority
            else :
                break

원소 제거(출력)

힙은 최소 혹은 최대 값을 쉽게 찾아내기 위해 고안된 자료형입니다. 따라서 삭제 연산은 루트 노드에서만 이루어집니다.

루트에서 삭제가 이루어지면 다음 루트 노드를 채울 값을 정해야 됩니다.

루트 노드의 값이 삭제가 되면 빈자리를 마지막 노드가 대신합니다.

이후 자식 노드와의 반복적인 비교와 변경을 통해 정렬을 시행 후 마무리됩니다.

 

힙은 입력과 삭제(출력) 모두 O(log n)의 시간 복잡도를 가집니다.

 

 

 python의 heapq라이브러리 

 

python의 heapq라이브러리는 힙을 편리하게 사용할 수 있을 메서드를 제공합니다.

heapq라이브러리는 기본적으로 최소 힙 min heap기능만을 동작합니다.

import heapq		

data = [1,2,3,4]

heapq.heapify(data)		# 기존 데이터를 힙 구조로 재배치

heapq.heappush(data, 5)		# 힙 원소 추가
heapq.heappop(data)		# 힙 원소 삭제

 

최대 힙 max heap을 사용하기 위해서는 매개 데이터에 약간의 변화를 줘야 됩니다.

원소를 삽입, 삭제할 시 튜플로 원소로 묶어, 힙에서는 튜플 내에서 맨 앞의 값을 기준으로 최소 힙이 구성되는 원리를 이용해 사용할 수 있습니다.

즉  (우선순위, 값) 구조 의 튜플을 힙에 추가하거나 삭제하면 됩니다.

 

import heapq

data= [1,2,3,4]
heap = []

for num in data:
  heapq.heappush(heap, (-num, num))  # (우선 순위, 값)