[자료구조] 힙

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

# 최소힙구현
class BinaryHeap:
    def __init__(self):
        self.items = [None]
    def __len__(self):
        return len(self.items) - 1

    # 삽입 : O(logn)
    # 반복 구조
    def _percolate_up(self):
        # 배열 가장 마지막에 먼저 삽입
        i = len(self)
        parent = i // 2
        # 부모가 더 큰 값을 가지는 경우 스왑
        while parent > 0:
            if self.items[i] < self.items[parent]:
                self.items[parent], self.itmes[i] = \
                    self.items[i], self.items[parent]
                i = parent
                parent = i // 2
                
    def insert(self, k):
        self.items.append(k)
        self._percolate_up()

    # 추출 : O(logn)
    # 재귀 구조
    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