Heaps & Priority Queues

1. Overview

힙과 우선순위 큐(Heaps & Priority Queues)는 수백만 개의 원소 중에서 "지금 가장 중요한(우선순위 최고) 녀석을 O(log n) 안에 추출하고, 새 녀석도 O(log n) 안에 끼워 넣는" 완전 이진 트리(Complete Binary Tree) 기반의 극강 효율 추상 자료형입니다.

학습자는 배열 하나가 완전 이진 트리처럼 동작하는 **배열 기반 힙(Heap)의 인덱스 마법(parent: i//2, children: 2i, 2i+1)**을 뜯어봅니다. 나아가 최소 힙(Min-Heap, 루트 = 최솟값)과 최대 힙(Max-Heap)의 힙 속성(Heap Property) 유지 연산(Heapify Up/Down)을 거쳐, 힙 정렬(Heap Sort)의 O(n log n) + O(1) 공간의 위대함, 그리고 다익스트라(Dijkstra) 최단 경로, Huffman 인코딩, K-way 병합(K-way Merge) 같은 실무 핵심 알고리즘 엔진으로서의 힙 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• 배열 기반 힙 (Array Heap): 인덱스 산술(Index Arithmetic), Heapify-Up(삽입 후 버블 업), Heapify-Down(루트 삭제 후 시프트 다운), Build-Heap O(n).
• 힙 정렬 (Heap Sort): O(n log n) 시간 + O(1) 추가 공간 정렬, In-place 특성.
• 우선순위 큐 응용 (Priority Queue Applications): 다익스트라(Dijkstra) 최단 경로, Prim MST, Huffman Encoding, Top-K Elements, K-way Merge.
• 피보나치 힙 개요 (Fibonacci Heap Intro): 다익스트라에서 decrease-key를 O(1) 분할 상환으로 지원하는 이론적 최적.

Out-of-Scope

• 완전 이진 트리 외 균형 트리 구조: AVL/RB 트리 등 포인터 기반 트리 $\rightarrow$ 04-02-01. Binary Trees 영역.
• 스케줄링 다단계 피드백 큐: OS 커널 레벨의 우선순위 큐 $\rightarrow$ 03-02-03. CPU Scheduling 영역.

Boundaries

• Heap vs BST (Priority Queue): 힙(Min-Heap)은 최솟값 추출 O(log n)이 완벽하지만, k번째 최솟값 탐색은 O(k log n)으로 비효율적이고 임의 원소 탐색이 O(n)입니다. BST(std::map)는 임의 원소 탐색 O(log n)과 범위 쿼리가 가능하지만 구현이 복잡합니다. 우선순위 기반 추출만 필요하면 힙, 정렬된 컬렉션에서 범위 쿼리도 필요하면 BST를 선택합니다.

3. Counterexample

• Max-Heap 삭제 후 루트 재삽입 실수 (Delete Min Trap in Max-Heap): 최댓값 추출 후 힙 재정렬을 위해 "가장 큰 자식을 루트에 올려야지"라며 루트를 그냥 삭제하고 자식 노드를 루트로 승격시키는 순진한 코드. 배열 기반 힙에서 임의의 노드를 삭제하면 완전 이진 트리(Complete Binary Tree) 형태가 깨져 인덱스 산술(parent=i//2, children=2i, 2i+1)이 모두 무효해집니다. 반드시 마지막 원소(배열의 맨 끝)를 루트로 옮기고 Heapify-Down을 수행해야 완전 이진 트리 형태가 유지됩니다.
• Build-Heap을 n번 Insert로 오해 (Build-Heap O(n) Misunderstanding): "힙을 만들려면 원소를 하나씩 n번 Insert(Heapify-Up)하면 되니까 O(n log n)이야"라는 통념적 오해. 사실 배열 전체를 힙으로 만드는 Build-Heap 알고리즘은 배열 절반(내부 노드)에 대해 Heapify-Down을 밑에서 위로 수행하며, 수학적으로 O(n) 시간에 완료됩니다(하위 레벨 노드가 많고 이동 거리가 짧아 합이 수렴). n번 Insert O(n log n)과 Build-Heap O(n)의 차이는 100만 원소에서 Heap Sort 성능을 2배 이상 바꿉니다.

4. Prerequisites

• 완전 이진 트리 (Basic): 모든 레벨이 꽉 찬 이진 트리(Complete Binary Tree)가 왜 배열로 낭비 없이 표현 가능한지의 구조적 이해가 필요합니다. (04-02-01 Binary Trees)
• 인덱스 산술 (Basic): 1-인덱스 기준 parent = i//2, left = 2i, right = 2i+1 공식이 성립하는 이유를 배열 레이아웃과 연결해 이해해야 합니다.

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 배열이 트리가 되는 인덱스 마법, 힙의 해부 (Heap Array Anatomy)

• Why to Learn: 포인터 없이 배열의 인덱스 산술만으로 완벽한 이진 트리를 구현하고, 힙 속성(최솟값이 항상 루트)을 유지하는 "버블 업/다운"의 단순한 반복이 OS 스케줄러와 네트워크 라우터의 심장이 되는 역학을 꿰기 위함입니다.
• What to Learn:
  • Concepts: Min-Heap/Max-Heap 속성, 1-기반 인덱스(parent=i//2, L=2i, R=2i+1), Heapify-Up(삽입 후 부모와 교환), Heapify-Down(루트 삭제 후 자식과 교환).
  • Skills: push(v) O(log n), pop() O(log n), peek() O(1).
  • Tools: 파이썬 heapq 모듈(Min-Heap, Max-Heap은 -v로).
• How to Learn:
  • 1단계: Min-Heap에 [5] 다음 3 삽입: 배열 [5, 3]. 3의 부모 5 > 3이므로 교환 → [3, 5]. 다시 4 삽입: 배열 [3, 5, 4]. 4의 부모 3 < 4이므로 교환 없음. Heapify-Up 역학을 해부합니다.
  • 2단계: Pop: 루트(3) 추출, 마지막 원소(4)를 루트로 이동 → [4, 5]. 4의 자식들 중 최솟값(5) > 4이므로 교환 없음. Heapify-Down 종료. 결과 [4, 5]를 뜯어봅니다.
• Implement: 파이썬 MinHeap 클래스. _arr = [None] (1-인덱스)으로 시작. push(v), pop(), peek(), _heapify_up(i), _heapify_down(i) 구현. [5, 3, 7, 1, 8, 2] 순으로 push 후 연속 pop이 [1, 2, 3, 5, 7, 8] 정렬 순서임을 증명.

Recommended

Core Topic 02: O(n) 힙 건설과 제자리 정렬, Build-Heap과 Heap Sort (Heap Sort)

• Why to Learn: "100만 원소를 하나씩 Insert해서 힙 만들면 O(n log n)인데, Build-Heap은 왜 O(n)이야?"라는 의문의 수학적 해답과, 추가 메모리 없이 O(n log n) 정렬을 완료하는 In-place Heap Sort를 장악하기 위함입니다.
• What to Learn:
  • Concepts: Build-Heap O(n) 증명(Heapify-Down 총 이동 거리의 합 수렴), Heap Sort 2단계(Build-Max-Heap → 반복 Pop+배열 정렬).
  • Skills: In-place 정렬, 비교 정렬의 하한(Comparison Lower Bound) O(n log n) 최적성.
• How to Learn:
  • 1단계: [4, 10, 3, 5, 1] 배열을 Build-Max-Heap으로. 내부 노드는 인덱스 n//2 부터 1까지 역순으로 Heapify-Down 수행. 총 이동 횟수의 합이 O(n)임을 각 레벨에서의 노드 수 × 최대 이동 거리의 합으로 수학 증명합니다.
  • 2단계: Heap Sort: Max-Heap의 루트(최댓값)를 배열 끝으로 보내고 힙 크기를 줄이며 Heapify-Down 반복. 이 과정이 배열을 제자리(In-place)에서 정렬하는 역학을 뜯어봅니다.
• Implement: 파이썬 heap_sort(arr). build_max_heap() 후 루프에서 arr[0], arr[n-1] = arr[n-1], arr[0] 교환 + heapify_down(0, n-1). 랜덤 1000개 배열에 heap_sort 결과가 sorted() 결과와 일치함을 assert. 추가 메모리 tracemalloc 측정으로 O(1) 공간 In-place 증명.

Practical

Core Topic 03: 최단 경로의 엔진, 다익스트라와 Top-K 힙 패턴 (Dijkstra & Top-K)

• Why to Learn: 구글 지도의 최단 경로, 네트워크 라우팅 프로토콜(OSPF)의 Shortest Path First, 실시간 Top-K 트렌딩 아이템 계산의 공통 엔진이 바로 Min-Heap 우선순위 큐임을 꿰기 위함입니다.
• What to Learn:
  • Concepts: 다익스트라 알고리즘 O((V+E)log V with Min-Heap), Prim's MST, Top-K Frequent Elements, K번째 최솟값.
  • Skills: (distance, node) 튜플로 힙에 삽입하는 다익스트라 패턴, Lazy Deletion.
• How to Learn:
  • 1단계: 다익스트라의 핵심: (dist, node) 튜플을 Min-Heap에 Push. Pop 시 항상 현재까지 최단 거리 노드를 꺼내어 인접 노드 거리를 갱신하고 힙에 Push. 이미 방문된 노드는 dist가 갱신되지 않아 건너뜀(Lazy Deletion)하는 구조를 해부합니다.
  • 2단계: Top-K 원소: n개 원소 중 가장 큰 K개를 효율적으로 찾으려면, 크기 K의 Min-Heap을 유지하면서 새 원소가 힙의 루트(현재 Top-K 중 최솟값)보다 크면 루트를 빼고 새 원소를 삽입. O(n log K)로 완성되는 패턴을 뜯어봅니다.
• Implement: 파이썬 dijkstra(graph, start) + top_k_elements(arr, k). 다익스트라: heapq.heappush((dist, node)) 패턴으로 5개 노드 그래프 최단 경로 출력. Top-K: Min-Heap 크기 K로 [3,1,4,1,5,9,2,6]에서 K=3 최댓값 [5,6,9] 추출 증명.

Advanced

Core Topic 04: K-way 합병과 이론적 극한, K-way Merge와 Fibonacci Heap (Advanced Applications)

• Why to Learn: 분산 시스템에서 각 서버가 정렬된 로그 파일을 가지고 있을 때, K개의 정렬 파일을 하나의 정렬 파일로 병합하는 K-way Merge의 효율적 구현과, 다익스트라의 이론적 복잡도를 O((V+E)+V log V)로 끌어내리는 Fibonacci Heap의 개념을 장악하기 위해서입니다.
• What to Learn:
  • Concepts: K-way Merge O(n log K), LeetCode #23 Merge K Sorted Lists, Fibonacci Heap(Amortized O(1) decrease-key), 이론적 최적 MST 알고리즘.
  • Skills: 초기 K개 리스트 헤드로 Min-Heap 구성, Pop→처리→다음 원소 Push 패턴.
• How to Learn:
  • 1단계: K개의 정렬 리스트 [1,4,7],[2,5,8],[3,6,9](./1,4,7],[2,5,8],[3,6,9) 가 있을 때, 각 리스트 첫 원소 (1,0,0), (2,1,0), (3,2,0) (값, 리스트idx, 원소idx)를 Min-Heap에 Push. Pop하여 최솟값 출력, 해당 리스트의 다음 원소를 Push. 이 반복이 n개 원소 전체를 O(n log K)에 정렬하는 역학을 해부합니다.
  • 2단계: Fibonacci Heap 개요: 다익스트라에서 decrease-key 연산(더 짧은 경로 발견 시 거리 갱신)이 Binary Heap에선 O(log V)인데, Fibonacci Heap은 트리를 느슨하게 유지해 amortized O(1)로 decrease-key를 수행하여 이론적 O((V+E)+V log V) 최적을 달성합니다.
• Implement: 파이썬 merge_k_sorted(lists) 함수. heapq.heappush((val, list_idx, elem_idx)) 패턴으로 K=5 정렬 리스트 병합. [1,4,7],[2,5,8],[3,6,9],[0,10],[11](./1,4,7],[2,5,8],[3,6,9],[0,10],[11) → [0,1,2,3,4,5,6,7,8,9,10,11] 출력 검증. 전통적 K-1번 2-way merge(O(n·K))와 K-way Heap merge(O(n·log K)) 시간 비교 벤치마크.

7. Terminology

8. References

Primary

• [P2] SWEBOK v4.0 - Software Construction / Runtime Efficiency (Algorithms) — Priority ordering.
• [P1] CS2023 - AL/Algorithms and Complexity (Heaps) — Core requirements.

Secondary

• [Introduction to Algorithms (CLRS)] Cormen — Formal heap analysis and heapsort.
• [Data Structures and Algorithm Analysis in Java] Mark Allen Weiss — PQ implementation.

Industry

• [Python Docs: heapq — Heap queue algorithm] — Industry standard implementation.
• [CPP Reference: std::priority_queue] — STL container specification.

9. Final Checklist

Primary

• '힙(Heap)'이 왜 항상 '완전 이진 트리'여야만 하는지 배열 인덱스 사상의 물리적 관점에서 설명 가능한가? (P1)
• 힙에서 데이터를 삽입(Push)할 때 최대 소요 시간이 왜 트리의 높이($O(\log n)$)를 넘지 않는지 입증할 수 있는 가? (P1)

Secondary

• 무작위로 섞인 배열을 'Bottom-up Heapify' 방식으로 힙으로 만들 때, 왜 $O(n \log n)$이 아닌 $O(n)$이 소요되는지 수리적으로 소통 가능한가?
• 우선순위 큐를 구현할 때 '정렬된 연결 리스트'보다 '힙'이 왜 물리적으로 유연한 삽입 성능을 보이는지 도출할 수 있는 가?

Industry

• 실시간 OS 스케줄러 설계 시, 수만 개의 스레드 우선순위를 관리하기 위해 힙 구조가 왜 필수적인지 물리적 근거를 기술할 수 있는 가? (SFIA)
• 힙 정렬(Heap Sort)이 퀵 정렬(Quick Sort)보다 평균적으로 느림에도 불구하고 '최악의 경우' 안정성을 위해 채택되는 엔지니어링 케이스를 제안할 수 있는 가?