Python 힙 구현

힙 자료구조를 만족하려면 두 가지 조건(최소 힙 기준)

1. 부모 노드가 자식 노드보다 작다.

2. 트리의 모양이 완전 이진트리의 형태.

 

완전 이진트리는 마지막 레벨을 제외하고 모든 노드가 왼쪽에서 오른쪽으로 채워져 있는 트리

-> 리스트로 구현

class BinaryHeap:
    def __init__(self):
        self.items = [None]

    def __len__(self):
        return len(self.items) - 1

    # 위로 올라가는거
    def _percolate_up(self):
        index = len(self)
        parent = index // 2

        while parent > 0:
            if self.items[parent] > self.items[index]:
                self.items[parent], self.items[index] = self.items[index], self.items[parent]
                index = parent
                parent = index // 2
            else:
                break

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

    # 아래로 내려가는거
    def _percolate_down(self, index):
        left = index * 2
        right = index * 2 + 1
        smallest = index
        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 != index:
            self.items[index], self.items[smallest] = self.items[smallest], self.items[index]
            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