힙이란?

데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진트리(Complete Binary Tree)의 일종

최대 값 최소 값 연산에 대해서는 이진 힙의 시간 복잡도는 O(1)이다.

BST와 힙의 차이점

BST는 좌,우 대소관계를 보장하는 반면 이진 힙은 상,하 대소 관계를 보장한다.

삽입방법

1. 원소를 맨 마지막에 삽입
2. 부모노드와 비교 더 크다면 자리를 바꿈
3. 부모노드보다 작거나 루트노드 일 때까지 반복

삽입시 시간복잡도O(log(N))

삭제방법

스택 같이 맨위에 있는 루트노드만 삭제할 수 있습니다.
삭제 후 힙의 규칙을 지켜야합니다.

1. 루트 노드와 맨 끝에 있는 원소를 교체한다.
2. 맨 뒤에 있는 원소(기존 루트노드)를 삭제한다
3. 변경된 노드와 자식 노드들을 비교합니다. 두 자식 중 더 큰 자식과 비교해서 자신보다 자식이 더 크다면 자리를 바꿉니다.
4. 자식 노드 둘보다 부모 노드가 크거나 가장 바닥에 도달하지 않을 때까지 반복
5. 기존 루트노드를 반환합니다.

삭제시 시간복잡도 O(log(N))

파이썬으로 구현하기

파이썬에서는 최소 힙으로 heapq로 모듈이 이미 있다.
여기서는 최대 힙 구현을 해보겠습니다.

class BinaryMaxHeap:
    def __init__(self):
        # 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용한다.
        self.items = [None]

    def __len__(self):
        # len() 연산을 가능하게 하는 매직 메서드 덮어쓰기(Override).
        return len(self.items) - 1

    def _percolate_up(self):
        # percolate: 스며들다.
        cur = len(self)
        # left 라면 2*cur, right 라면 2*cur + 1 이므로 parent 는 항상 cur // 2
        parent = cur // 2

        while parent > 0:
            if self.items[cur] > self.items[parent]:
                self.items[cur], self.items[parent] = self.items[parent], self.items[cur]

            cur = parent
            parent = cur // 2
            
     def _percolate_down(self, cur):
        biggest = cur
        left = 2 * cur
        right = 2 * cur + 1

        if left <= len(self) and self.items[left] > self.items[biggest]:
            biggest = left

        if right <= len(self) and self.items[right] > self.items[biggest]:
            biggest = right

        if biggest != cur:
            self.items[cur], self.items[biggest] = self.items[biggest], self.items[cur]
            self._percolate_down(biggest)

    def insert(self, k):
        self.items.append(k)
        self._percolate_up()

    def extract(self):
        if len(self) < 1:
            return None

        root = self.items[1]
        self.items[1] = self.items[-1]
        self.items.pop()
        self._percolate_down(1)

        return root