Priority Queues and Heaps

Queue는 FIFO 구조라 먼저 들어온 것이 먼저 나간다. 근데 현실에서는 순서보다 중요도가 우선인 경우가 많다. 응급실을 생각해보면 — 먼저 온 경미한 환자보다 나중에 온 위급한 환자를 먼저 봐야 한다. 이럴 때 필요한 게 Priority Queue다.

---

1. Priority Queue (PQ)

각 entry가 (key, value) 쌍으로 저장된다. key가 우선순위를 결정하고, value는 실제 데이터다.

응급실 예시:

• key = 병증의 심각도
• value = 환자 정보

Methods

Method	설명
P.add(k, v)	key k, value v인 entry 추가
P.remove_min()	가장 작은 key의 entry를 꺼내서 반환
P.min()	가장 작은 key의 entry를 확인만 (제거 안 함)
P.is_empty()	비어있는지 확인
len(P)	entry 수 반환

List로 구현할 때의 trade-off

	Unsorted List	Sorted List
add	O(1) — 그냥 끝에 추가	O(n) — 자리 찾아야 함
remove_min	O(n) — 전체 탐색 필요	O(1) — 맨 앞에 있음

둘 다 한쪽이 느리다. 이 trade-off를 해결하는 게 Heap이다.

---

2. Heap

Heap은 두 가지 조건을 만족하는 binary tree다.

Heap-Order Property

• Min-heap: 부모 key ≤ 자식 key → 최솟값이 항상 root
• Max-heap: 부모 key ≥ 자식 key → 최댓값이 항상 root

Complete Binary Tree

• level 0 ~ h-1까지는 전부 꽉 차있고
• 마지막 level h는 왼쪽부터 채워져 있음

Complete binary tree여야 하는 이유는 height를 작게 유지하기 위해서다. 이 조건 덕분에 n개의 노드가 있을 때 height가 항상 ⌊log n⌋이 보장된다. Heap의 operations가 O(h)이기 때문에 결국 O(log n)이 된다.

        (4,C)          ← root = 최솟값
       /      \
    (5,A)    (6,Z)
    /   \    /   \
 (15,K)(9,F)(7,Q)(20,B)

---

3. Heap Operations

add(k, v) — Up-heap bubbling

Complete binary tree를 유지하려면 새 노드는 무조건 마지막 위치에 추가해야 한다. 근데 이러면 heap-order property가 깨질 수 있다.

해결책: 추가한 노드를 부모와 비교하면서 위로 swap — up-heap bubbling

1. 마지막 위치에 추가
2. 부모보다 key가 작으면 swap
3. heap-order property 만족할 때까지 반복

최악의 경우 root까지 올라가야 하므로 O(h) = O(log n)

remove_min() — Down-heap bubbling

Root를 그냥 삭제하면 트리가 두 개로 쪼개진다. 그래서 root를 바로 삭제하지 않는다.

해결책:

1. root와 last node를 swap
2. last node(원래 root) 삭제
3. 새 root를 더 작은 자식과 swap하면서 아래로 내려감
4. heap-order property 만족할 때까지 반복

내릴 때 더 작은 자식이랑 swap해야 한다. 큰 자식이랑 swap하면 그 자식이 sibling보다 작아져서 heap-order property가 또 깨지기 때문이다.

마찬가지로 O(h) = O(log n)

Time Complexity 비교

Operation	Unsorted List	Sorted List	Heap
add	O(1)	O(n)	O(log n)
remove_min	O(n)	O(1)	O(log n)
min	O(n)	O(1)	O(1)

Heap은 두 list 방식의 trade-off를 O(log n)으로 균형있게 해결한다. min은 항상 root에 있으니까 O(1).

---

4. Bottom-Up Heap Construction

n개의 원소로 heap을 만드는 두 가지 방법:

방법 1: add를 n번 → O(n log n)

방법 2: Bottom-up heap construction → O(n)

아이디어는 이렇다. n개를 그냥 트리에 배치한 뒤, 아래에서 위로 올라가면서 각 subtree를 down-heap으로 고쳐나간다.

아래 레벨부터:
[subtree 1] → down-heap
[subtree 2] → down-heap
...
점점 위로 올라가면서 전체를 heap으로 만듦

왜 O(n)이냐면, 아래 노드들은 down-heap을 거의 안 해도 되기 때문이다. 노드 수는 아래로 갈수록 많고, 위로 갈수록 적다. 많은 노드들이 조금만 이동하면 되니까 전체 합산하면 O(n)이 나온다.

add n번은 모든 노드가 최대 h번씩 이동하지만, bottom-up은 대부분의 노드가 조금만 이동하면 된다는 차이다.

---

5. Heap-Sort

Heap을 이용한 정렬이다. PQ로 정렬하는 방법(add n번 + remove_min n번)을 Heap으로 구현하면:

1. 주어진 리스트로 heap 만들기 (bottom-up construction: O(n))
2. remove_min()을 n번 반복 → 정렬된 순서로 출력 (O(n log n))

전체 시간복잡도: O(n log n)

Selection-sort, Insertion-sort가 O(n²)인 것과 비교하면 훨씬 빠르다.

용어 정리

• Heapify: 배열로부터 heap을 만드는 것
• Bottom-up heap construction: O(n)의 효율적인 heapify 알고리즘
• Up-heap / Down-heap: heap-order property를 위반한 노드를 고치는 것

---

6. 정리

Queue는 순서만 고려하지만, PQ는 우선순위를 고려한다. List로 PQ를 구현하면 add나 remove_min 중 하나가 반드시 느려지는 trade-off가 생긴다. Heap은 complete binary tree의 구조 덕분에 height가 항상 O(log n)으로 유지되어 이 trade-off를 균형있게 해결한다. 여기에 정렬까지 적용한 게 Heap-Sort로, O(n log n)의 시간복잡도를 가진다.