Heap

우선순위 큐(Priority Queue)와 Heap의 관계

우선순위 큐(Priority Queue)와 Heap의 관계에 대해 알아보겠습니다. 우선순위 큐는 운영체제(OS)에서 프로세스들의 우선순위를 부여하거나, 애플리케이션에서 프리미엄 회원의 요청을 먼저 처리하는 등 우선순위가 있는 대상을 관리할 때 사용됩니다. 이때, 우선순위 큐는 가장 높은 우선순위를 가진 원소를 빠르게 반환하고 삭제할 수 있어야 합니다. 이를 위해 효율적으로 우선순위를 다루는 자료구조로 Heap이 사용됩니다.

Heap

Heap은 대표적인 우선순위 큐를 구현하기 위한 자료구조 중 하나로, 특히 Binary Heap이 널리 사용됩니다. Binary Heap은 다음 두 가지 조건을 만족하는 완전 이진 트리입니다.
1. 모든 부모 노드가 자식 노드보다 크거나 같은 값을 갖는다.
2. 완전 이진 트리(Complete Binary Tree) 구조를 유지한다.

이진 힙은 최대 힙(Max heap)과 최소 힙(Min heap)으로 나눌 수 있습니다. 최대 힙은 루트 노드가 가장 큰 값을 갖고, 최소 힙은 루트 노드가 가장 작은 값을 갖습니다.

완전 이진 트리(Complete Binary Tree)

완전 이진 트리란 모든 레벨이 완전히 채워져 있고, 마지막 레벨에서는 노드들이 왼쪽부터 차례대로 채워진 이진 트리를 의미합니다. 이러한 구조로 인해 완전 이진 트리는 배열로 표현할 수 있어서 효율적인 구현이 가능합니다.

완전 이진 트리(Complete Binary Tree) → 배열(Array)로 표현 가능

완전 이진 트리의 특성 때문에 각 노드의 위치를 배열의 인덱스로 표현하기 쉽습니다. 루트 노드는 배열의 인덱스 1에 위치하고, 다음 레벨의 노드들은 왼쪽부터 오른쪽으로 순차적으로 인덱스를 할당합니다. 이를 통해 배열 인덱스를 이용하여 트리의 각 노드의 관계를 파악하고 조작할 수 있습니다.

• 왼쪽 자식 노드 : array[2i+1]
• 오른쪽 자식 노드 : array[2i+2]
• 부모 노드 : array[(i-1)/2]

Heap Operation

---

Heapify

Heapify는 주어진 배열을 힙 구조로 만들기 위한 과정입니다. 완전 이진 트리 구조를 유지하면서 힙 조건을 만족하도록 배열을 조정합니다. 다음과 같은 단계로 이루어집니다:

• 주어진 배열은 대응되는 완전 이진 트리로 간주합니다.
• 트리에서 가장 마지막 노드부터 시작하여 부모 노드와 비교하며 힙 조건을 만족시킵니다.

삽입(push)

Max Heap에 새로운 원소를 삽입할 때, 해당 원소는 먼저 배열의 끝에 추가되고, 상위 노드로 이동하며 힙을 조정합니다. 과정은 다음과 같습니다:

• 새로운 원소를 힙 배열의 끝에 추가합니다.
• 자식과 부모를 비교하고, 자식의 값이 부모의 값보다 크다면 두 노드를 교환합니다.
• 이 과정을 반복하여 힙의 특성을 만족시킵니다.

Heap에서 최대 원소를 삭제하며 반환 (pop)

최대힙(Max Heap)에서 최대 원소를 삭제할 때는 루트 노드를 삭제하고 반환합니다. 이때, 루트 노드를 삭제하면 완전 이진 트리의 구조가 깨지므로, 맨 끝 노드를 루트로 복사한 뒤 서브 트리를 힙으로 조정합니다.

• 맨 끝 노드를 루트로 복사합니다.
• 루트를 기준으로 자식과 비교하여 더 큰 자식과 교환합니다.
• 이 과정을 반복하여 힙의 특성을 유지합니다.

구현 코드

class Heap:
    def __init__(self, capacity):
        self.array = [0] * capacity  # 배열 초기화
        self.n = 0  # 원소 개수 초기화

    def push(self, e):
        if self.n == len(self.array):
            raise Exception("Heap Overflow")

        self.array[self.n] = e  # 배열의 끝에 원소 추가
        self.bubble_up(self.n)  # 원소를 올바른 위치로 이동
        self.n += 1

    def bubble_up(self, i):
        child = i
        parent = (i - 1) // 2

        # 부모와 자식 노드를 비교하며 힙 특성 유지
        while parent >= 0 and self.array[child] > self.array[parent]:
            self.array[child], self.array[parent] = self.array[parent], self.array[child]  # 스왑
            child = parent
            parent = (child - 1) // 2

    def pop(self):
        if self.n == 0:
            raise Exception("Heap Underflow")

        max_value = self.array[0]  # 최대값은 루트 노드에 있음
        self.array[0] = self.array[self.n - 1]  # 루트 노드를 맨 끝 노드로 대체
        self.n -= 1
        self.bubble_down(0)  # 원소를 올바른 위치로 이동

        return max_value

    def bubble_down(self, i):
        parent = i

        # 자식 노드와 부모 노드를 비교하며 힙 특성 유지
        while True:
            left_child = 2 * parent + 1
            right_child = 2 * parent + 2

            largest = parent

            if left_child < self.n and self.array[left_child] > self.array[largest]:
                largest = left_child

            if right_child < self.n and self.array[right_child] > self.array[largest]:
                largest = right_child

            if largest == parent:
                break

            self.array[parent], self.array[largest] = self.array[largest], self.array[parent]  # 스왑
            parent = largest

    def heapify(self):
        # 리프노드가 아닌 최초의 노드부터 시작하여 heapify 수행
        for i in range((self.n - 2) // 2, -1, -1):
            self.bubble_down(i)