힙

** 정의

데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리

 

**구현하는 법

힙은 큰 값이 상위 레벨에, 작은 값이 하위 레벨에 있도록 하는 자료구조

      8      Level 0
    6   3    Level 1
     2 1     Level 2  # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아닙니다!

      8      Level 0
    6   3    Level 1  # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
   4 2 1     Level 2  # 자식 노드보다 크니까 **힙이 맞습니다!**

      8      Level 0
    6   **3**    Level 1  # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
   4 2 **5**     Level 2  # 자식 노드보다 크지 않아서 **힙이 아닙니다..!**
											

힙은 최솟값을 맨 위로, 최댓값을 맨 위로 올릴 수도 있다

 

최솟값이 맨 위면 Min Heap, 최댓값이 맨 위면 Max Heap 이라고 함.

 

 

 

계산 편의를 위해 인덱스를 1부터 사용,

(parent: x, left: 2x, right: 2x+1)

 

실제 구현 순서

 

- 원소를 맨 마지막에 넣는다.

- 부모 노드와 비교

- 더 크다면 자리를 바꿔준다.

- 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 과정을 반복

이 맥스 힙에서 9를 추가해보겠습니다!
      8      Level 0
    6   3    Level 1  
   4 2 1     Level 2 

1. 맨 마지막에 원소를 넣습니다.

      8      Level 0
    6   3    Level 1  
   4 2 1 **9**   Level 2 

2-1. 부모 노드와 비교합니다. 3보다 9가 더 크니까! 둘의 자리를 변경합니다.

      8      Level 0
    6   **3**    Level 1  
   4 2 1 **9**   Level 2 

      8      Level 0
    6   **9**    Level 1  
   4 2 1 **3**   Level 2 

2-2. 다시 부모 노드와 비교합니다. 8보다 9가 더 크니까! 둘의 자리를 변경합니다.

      **8**      Level 0
    6   **9**    Level 1  
   4 2 1 3   Level 2 

      **9**      Level 0
    6   **8**    Level 1  
   4 2 1 3   Level 2 

3. 가장 위에 도달했으므로 멈춥니다. 힙의 특성을 그대로 유지해 데이터를 삽입했습니다!

      **9**      Level 0
    6   **8**    Level 1  
   4 2 1 3   Level 2

 

 

**최대 힙 - 시간 복잡도

O(log(N))

 

**실제 구현

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