CS학습2026년 8월 18일

Heap: 우선순위 큐를 효율적으로 구현하는 자료구조

힙(Heap)은 최댓값 또는 최솟값을 빠르게 찾도록 설계된 트리 기반의 자료구조입니다. 완전 이진 트리(Complete Binary Tree)의 특성을 가지며, 주로 우선순위 큐(Priority Queue)를 구현하는 데 사용됩니다. 힙은 배열을 이용하여 효과적으로 구현될 수 있습니다.

송민성3분 읽기

1. 개념

힙(Heap)은 다음 조건을 만족하는 트리 기반 자료구조입니다.

Heap Property: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같습니다 (최대 힙, Max Heap). 또는 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같습니다 (최소 힙, Min Heap).
Complete Binary Tree: 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 노드는 왼쪽부터 채워져 있습니다.

최대 힙의 경우, 루트 노드는 항상 가장 큰 값을 가집니다. 최소 힙의 경우, 루트 노드는 항상 가장 작은 값을 가집니다.

2. 왜 사용하는가

힙은 다음과 같은 경우에 유용합니다.

우선순위 큐 구현: 우선순위가 높은 요소부터 처리해야 하는 상황에서 효율적인 자료구조입니다.
정렬 알고리즘: 힙 정렬(Heap Sort)은 힙 자료구조를 이용하여 데이터를 정렬하는 알고리즘입니다.
최소/최대 K개 요소 찾기: 데이터 스트림에서 가장 작은 또는 가장 큰 K개의 요소를 효율적으로 유지하고 관리할 수 있습니다.

3. 동작 원리

힙은 보통 배열로 구현됩니다. 배열의 0번째 인덱스는 사용하지 않고, 1번째 인덱스부터 힙의 요소를 저장합니다. 부모 노드와 자식 노드의 관계는 다음과 같습니다.

노드 i의 부모 노드: i / 2
노드 i의 왼쪽 자식 노드: 2 * i
노드 i의 오른쪽 자식 노드: 2 * i + 1

힙 연산 중 중요한 것은 heapify 연산입니다. heapify는 주어진 노드를 루트로 하는 서브트리가 힙 속성을 만족하도록 재정렬하는 연산입니다.

4. 코드 예제

다음은 Python으로 최대 힙(Max Heap)을 구현하는 예제입니다.

python

class MaxHeap:
    def __init__(self):
        self.heap = []

    def insert(self, value):
        self.heap.append(value)
        self._heapify_up(len(self.heap) - 1)

    def extract_max(self):
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()

        max_value = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0)
        return max_value

    def _heapify_up(self, index):
        parent_index = index // 2
        if parent_index > 0 and self.heap[index] > self.heap[parent_index]:
            self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]
            self._heapify_up(parent_index)

    def _heapify_down(self, index):
        left_child_index = 2 * index + 1
        right_child_index = 2 * index + 2
        largest = index

        if left_child_index < len(self.heap) and self.heap[left_child_index] > self.heap[largest]:
            largest = left_child_index

        if right_child_index < len(self.heap) and self.heap[right_child_index] > self.heap[largest]:
            largest = right_child_index

        if largest != index:
            self.heap[index], self.heap[largest] = self.heap[largest], self.heap[index]
            self._heapify_down(largest)

# Example
heap = MaxHeap()
heap.insert(5)
heap.insert(10)
heap.insert(2)
heap.insert(8)

print(heap.extract_max())  # Output: 10
print(heap.extract_max())  # Output: 8
print(heap.extract_max())  # Output: 5
print(heap.extract_max())  # Output: 2

5. 시간 복잡도 또는 성능 특성

Insert (삽입): O(log n) - 힙 속성을 유지하기 위해 heapify_up 연산을 수행합니다.
Extract Max/Min (최대/최소 값 추출): O(log n) - 루트 노드를 제거하고 heapify_down 연산을 수행합니다.
Heapify (힙 구성): O(n) - 배열을 힙으로 변환하는 연산입니다.

6. 실무 사용 사례

우선순위 기반 스케줄링: 운영체제에서 프로세스 스케줄링에 사용될 수 있습니다.
네트워크 라우팅: 최단 경로를 빠르게 찾기 위해 사용될 수 있습니다.
데이터 압축: Huffman 코딩과 같은 데이터 압축 알고리즘에서 사용될 수 있습니다.

7. 주의할 점

힙은 완전 이진 트리의 특성을 유지해야 합니다.
heapify 연산은 힙 속성을 유지하는 데 중요합니다.
최대 힙과 최소 힙을 명확하게 구분하여 사용해야 합니다.

8. 핵심 정리

힙은 우선순위 큐를 효율적으로 구현하는 데 유용한 자료구조입니다. 힙의 핵심은 힙 속성을 유지하면서 트리를 재정렬하는 heapify 연산입니다. 삽입 및 삭제 연산은 O(log n)의 시간 복잡도를 가지며, 힙 정렬과 같은 다양한 알고리즘에 활용될 수 있습니다.