[자료구조] 힙

📣 힙(Heap) 이란?

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조로서 다음과 같은 힙 속성을 만족한다.

📌 부모와 자식노드간의 대소 관계 존재

예를 들어, A가 B의 부모노드일 경우, A의 key값과 B의 key값 사이에는 대소관계가 성립한다. 키값의 대소관계는 오직 부모자식노드 간에만 발생, 형제노드끼리는 상관이 없다. -> 이진탐색트리와의 차이점이라고 볼 수 있다.

📌 최대힙 그리고 최소힙

힙은 딱 2가지의 종류로 나뉘어지는데 부모노드의 키값이 자식노드의 키값보다 항상 큰 '최대힙', 그리고 부모노드의 키값이 자식노드의 키값보다 항상 작은 '최소힙'이 있다.

📌 우선순위 최상위 or 최하위 노드 -> 뿌리노드

힙에서는 가장 높은(혹은 가장 낮은) 우선 순위를 가지는 노드가 항상 root노드에 오게 되는 특징이 있다. 이를 응용하면 자동으로 최소힙을 구현하는 python의 내장 모듈 heapq에서도 최대힙을 구현해낼 수 있다.

🔍 정의와 특성에 따라 힙 찾기!

   5
 3   4
   1   2  ❌ 완전이진트리가 아니라 힙이 아니다.
------------------------------------------------
   5
 3   1
2 4     ❌ 자식노드가 부모노드보다 커서 힙이 아니다.
   

👊 최대힙 자료구조 직접 구현해보기

class BinaryMaxHeap:
    def __init__(self):
        # None으로 시작하는 하나의 배열을 만든다.
        self.items = [None]

    def __len__(self):
        # magic function
        # index 1부터 시작하니 기본 len 함수보다 1 작다.
        return len(self.items) - 1

    def _percolate_up(self):
        # 가장 위에 도달할 때까지 부모요소와 크기를 비교합니다.
        # 부모요소보다 클 때까지 반복합니다.
        cur = len(self)
        parent = cur // 2

        # value 값을 바꿔주는 부분
        while parent > 0:
            if self.items[cur] > self.items[parent]:
                self.items[cur], self.items[parent] = self.items[parent], self.items[cur]

            # index 값을 바꿔주는 부분
            cur = parent
            parent = cur // 2


    def _percolate_down(self, cur):
        # 자식노드가 더 클 경우, 부모노드와 자리를 바꿉니다.
        
        biggest = cur
        left = 2 * cur
        right = 2 * cur + 1

        # if 문 두개로 자식노드 중 더 큰 키값을 가진 노드와 자리를 바꾸게 됩니다.
        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

		# 만일 여기서 biggest와 cur이 같다면 부모노드가 자식노드보다 크다는 것.
        # 더이상 down 할 필요가 없음
        if biggest != cur:
            self.items[cur], self.items[biggest] = self.items[biggest], self.items[cur]
            self._percolate_down(biggest)


    def insert(self, k):
        # 배열의 마지막에 요소를 추가한 다음에 percolate_up을 계속해서 실시합니다.
        self.items.append(k)
        self._percolate_up()

    def extract(self):
        # 루트 노드와 제일 마지막 노드를 바꾸고 가장 마지막 요소를 제거합니다.
        # 인덱스 1에서부터 아래로 계속해서 내려갑니다.
        # 원래 root 노드였던 것을 반환합니다.

        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

📘 메모할 내용

1. 시작할 때 self.items에 None값을 넣고 시작하는 이유는 heap의 index를 1부터 시작하기 위함이다. 이렇게 해야 아래로 내려갈 때 left index를 2 parent, right index를 2 parent + 1로 해줄 수 있다.