[자료 구조] 힙 (Heap)

최대 힙 - 삽입

힙이란?

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

• 최대/최소의 값들이 필요한 연산에 사용
• Max 힙 : 최댓값이 맨 위
• Min 힙 : 최솟값이 맨 위

      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  #   모든 부모 노드의 값이 자식 노드보다 크므로 힙O


      8      Level 0
    6   3    Level 1  # -> 이진 트리 O 완전 이진 트리 O 
   4 2 5     Level 2  # 모든 부모 노드의 값이자식 노드보다 크지 않으므로 힙이 아님

최대 힙 - 삽입 알고리즘

1. 원소를 맨 마지막에 넣는다.
2. 부모 노드와 비교, 더 크면 자리 바꾸기
3. 부모 노드보다 작거나 가장 위에 도달하지 않을 때 까지 반복

아래 Max 힙에서 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))
-> 반복하는 최대 횟수 : O(log(N))
-> Max 힙의 원소 추가는 O(log(N)) 의 시간 복잡도

최대 힙 삽입 구현

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

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

    def _percolate_up(self):
        # percolate: 스며들다.
        cur = len(self.items) - 1
        # 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

최대 힙 - 추출

최대 힙 - 추출 알고리즘

최대 힙에서 원소를 추출하는 방법 : 루트 노드(최댓값) 삭제 👉 맨 위 원소만 삭제 가능

아래 Max 힙에서 원소 제거하기 (항상 맨 위의 루트 노드가 제거)
      8      Level 0
    6   7    Level 1  
   2 5 4 3   Level 2 

1. 루트 노드와 맨 끝에 있는 원소 교체

      8      Level 0
    6   7    Level 1  
   2 5 4 3   Level 2 

      3      Level 0
    7   6    Level 1  
   2 5 4 8   Level 2 

2. 맨 뒤에 있는 원소 삭제
- > 기존 맥스힙에 있던 가장 큰 값 / 따라서 이 값을 마지막에는 반환해줘야 함

      3      Level 0
    6   7    Level 1  
   2 5 4 X   Level 2 

3-1. 변경된 노드를 더 큰 자식 노드와 비교  
    부모와 왼쪽 자식 비교 / 부모와 오른쪽 자식 비교 
    부모보다 큰 자식 중, 더 큰 자식과 변경해야 함
    7 > 6, 부모인 3 < 7 -> 둘의 자리를 변경합니다.

      3      Level 0
    6   7    Level 1  
   2 5 4     Level 2 

      7      Level 0
    6   3    Level 1  
   2 5 4     Level 2 

3-2. 다시 자식 노드와 비교 
    부모와 왼쪽 자식 비교 
    왼쪽 자식 4 > 부모 3 -> 둘의 자리를 변경 

      7      Level 0
    6   3    Level 1  
   2 5 4     Level 2 

      7      Level 0
    6   4    Level 1  
   2 5 3     Level 2 


4. 가장 아래 레벨에 도달 - 멈춤

      7      Level 0
    6   4    Level 1  
   2 5 3     Level 2 

5. 아까 제거한 원래 루트 노드, 8을 반환 

최대 힙 - 추출 시간복잡도

O(log(N))​

최대 힙 구현

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

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

    def _percolate_up(self):
        # percolate: 스며들다.
        cur = len(self.items) - 1
        # 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 extract(self):
        if len(self.items) - 1 < 1:
            return None

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

        return root

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

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

        if right <= len(self.items) - 1 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)