배열로 Heap 구현 예시

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

    def __len__(self):
        return len(self.items) - 1  # 배열의 마지막 인덱스를 가리키게끔 함

    def _percolate_up(self):  # insert에서 쓰일 내부 함수이므로 앞에 _를 붙임
        idx = len(self)
        parent = idx // 2
        while parent > 0:
            if self.items[idx] < self.items[parent]:
                self.items[parent], self.items[idx] = self.items[idx], self.items[parent]
            idx = parent
            parent = idx // 2

    def insert(self, k):
        self.items.append(k)  # 일단 맨 뒤에 붙인 후
        self._percolate_up()  # 최소 힙을 만족할 때 까지 자식, 부모 값 계속 변경

    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[left] < 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

 

출처

https://search.shopping.naver.com/book/catalog/32456486633?cat_id=50010920&frm=PBOKMOD&query=%ED%8C%8C%EC%9D%B4%EC%8D%AC+%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98+%EC%9D%B8%ED%84%B0%EB%B7%B0&NaPm=ct%3Dl7x0gr9c%7Cci%3D37450ff6270b8d3a48291e8dd82bcdc4e2f38eba%7Ctr%3Dboknx%7Csn%3D95694%7Chk%3Dd52b61344c06ba5a9592667b4cfc72998c53613e 

파이썬 알고리즘 인터뷰 : 네이버 도서