[자료구조] 힙(Heap)

1. 힙이란

힙은 완전 이진트리를 기반으로 하는 자료구조로서, 여러 값 중에서 최댓값이나 최솟값을 빠르게 찾기 위하여 고안되었다.

우선순위 큐에 활용된다.

 

2. 힙의 특징

• 힙은 최소 힙과 최대 힙으로 나눠지며 각각 아래의 특성을 만족한다.
  • 최소 힙(Min Heap)의 경우 부모가 자식보다 작거나 같다.
  • 최대 힙(Max Heap)의 경우 부모가 자식보다 크거나 같다.
• 중복 값을 허용한다.
• 정렬된 구조가 아니다. 최소 힙의 경우 부모가 자식보다 작거나 같다는 조건만 만족할 뿐 정렬되어 있지 않다. 예를 들어 오른쪽 자식 노드가 레벨 차이에도 불구하고 왼쪽 노드보다 더 작은 경우도 있을 수 있다. 
• 자식이 둘인 힙은 특별히 이진 힙이라고 부르고 자주 사용된다.

 

3. 힙의 구현

• 힙은 주로 배열로 구현한다.
• 직관적이고 쉽게 구현하기 위하여 인덱스 0은 사용하지 않고 1부터 사용한다.
• 부모 노드와 자식 노드의 관계
  • 왼쪽 자식의 인덱스 = 부모의 인덱스 * 2
  • 오른쪽 자식의 인덱스 = 부모의 인덱스 * 2 + 1
  • 부모의 인덱스 = 자식의 인덱스 // 2

3.1 힙의 삽입

1. 요소를 가장 하위레벨 최대한 왼쪽으로 삽입(배열로 표현할 경우 가장 마지막에 삽입)
2. 부모값과 비교해 값이 더 작은 경우 위치 변경
3. 계속해서 부모 값과 비교해 위치 변경

※ 시간복잡도는 O(logn)

 

 

3.2 힙의 추출(삭제)

1. 루트를 추출한다.
2. 추출 이후 아래의 과정으로 다시 힙의 특성을 유지한다.
3. 추출 이후 비어 있는 루트에 가장 마지막 요소가 올라간다.
4. 자식 노드와 값을 비교해서 자식보다 크다면 내려가는 과정을 반복한다.

※ 시간복잡도는 단순히 추출은 O(1)이나, 힙 유지에 O(logn) 소요

 

3.3 파이썬으로 이진 힙 구현

class BinaryHeap(object):
    def __init__(self):
        self.items = [None] #don't use index 0 
    
    def __len__(self):
        return len(self.items) - 1
    
    # when, number k is inserted, swap when it is smaller than parent
    def _percolate_up(self):
        i = len(self)
        parent = i // 2
        while parent > 0:
            if self.items[i] < self.items[parent]:
                self.items[parent], self.items[i] = self.items[i], self.items[parent]
            i = parent
            parent = i // 2
   
    # append number k and percolate_up
    def insert(self, k):
        self.items.append(k)
        self._percolate_up()
    
    
    # when extracting first item, move last item to first and swap with child when it is smaller than child
    def _percolate_down(self, idx):
        left = idx * 2
        right = idx * 2 + 1
        smallest = idx
        
        if left <= len(self) and self.items[left] < self.items[smallest]:
            smallest = left
        
        if right <= len(self) and self.items[right] < self.items[smallest]:
            smallest = right
        
        if smallest != idx:
            self.items[idx], self.items[smallest] = self.items[smallest], self.items[idx]
            self._percolate_down(smallest)
            
    def extract(self):
        extracted = self.items[1]
        self.items[1] = self.items[len(self)]
        self.items.pop()
        self._percolate_down(1)
        return extracted