Lecture 8: Binary Heaps 바이너리 힙, 이진 힙
Lecture 8: Binary Heaps
바이너리 힙은 특정 연산에 최적화된 트리 기반의 자료구조입니다.
주로 우선순위 큐(priority queue)를 구현하는 데 사용됩니다.
1. Priority Queue Interface
이전에 배운 자료 구조
* Stack: 가장 나중에 삽입된 데이터 먼저 뺌
* Queue: 가장 먼저 삽입된 데이터 먼저 뺌
오늘 배울 우선 순위 큐
가장 우선 순위가 높은 데이터를 먼저 뺌
트리에서 root에 위치한 데이터
Priority Queue Interface
여러 항목을 관리하면서, 가장 중요한(우선순위가 높은) 항목을 빠르게 접근하거나 제거할 수 있도록 합니다.
• Keep track of many items, quickly access/remove the most important
여러 항목을 저장하면서, 그 중 가장 중요한 항목을 빠르게 찾고 제거할 수 있어야 합니다.
– Example: router with limited bandwidth, must prioritize certain kinds of messages
예: 대역폭이 제한된 라우터는 특정 유형의 메시지를 우선적으로 처리해야 합니다.
(즉, 중요한 메시지부터 전송)
– Example: process scheduling in operating system kernels
예: 운영체제 커널에서의 프로세스 스케줄링. 더 높은 우선순위의 작업이 먼저 실행되어야 합니다.
– Example: discrete-event simulation (when is next occurring event?)
예: 이산 이벤트 시뮬레이션. 다음 이벤트가 언제 일어나는지를 빠르게 알아야 합니다 (우선순위가 가장 높은 이벤트가 먼저 발생).
– Example: graph algorithms (later in the course)
예: 그래프 알고리즘 (예: 다익스트라 알고리즘)에서도 사용됩니다. 우선순위 큐가 핵심입니다.
• Order items by key = priority so Set interface (not Sequence interface)
항목들은 키(=우선순위) 에 따라 정렬되며, 이는 Set 인터페이스 (순서보다는 정렬/검색에 초점) 기반이지,
순서를 유지하는 Sequence 인터페이스는 아닙니다.
• Optimized for a particular subset of Set operations:
Set 자료구조가 제공하는 모든 연산이 아니라, 일부 연산에 초점을 맞춰 최적화되어 있습니다.
build(X): build priority queue from iterable X
build(X)는 반복 가능한 객체 X로부터 우선순위 큐를 초기화하는 연산입니다.
초기 데이터를 한꺼번에 넣을 수 있습니다.
insert(x): add item x to data structure
insert(x)는 항목 x를 우선순위 큐에 추가하는 연산입니다.
delete_max(): remove and return stored item with largest key
delete max()는 가장 우선순위가 높은(키가 가장 큰) 항목을 제거하고 반환합니다.
find_max(): return stored item with largest key
find max()는 가장 우선순위가 높은 항목을 반환하지만, 제거하지는 않습니다.
• (Usually optimized for max or min, not both)
보통 한쪽만 (최댓값 또는 최솟값) 빠르게 처리할 수 있도록 설계되어 있습니다.
• Focus on insert and delete max operations: build can repeatedly insert;
우선순위 큐는 insert(삽입) 와 delete max(최댓값 삭제) 연산에 특히 초점이 맞춰져 있습니다.
build는 여러 번 insert 를 반복하는 방식으로도 구현할 수 있습니다.
find max() can insert(delete min())
find max()는 insert와 delete min()을 조합해서도 구현할 수 있습니다.
필요에 따라 우선순위 반대로 구성할 수도 있습니다 (min-heap vs max-heap).
2. Priority Queue Sort
우선순위 큐 자료구조를 이용하여 정렬 알고리즘을 만들 수 있습니다.
• Any priority queue data structure translates into a sorting algorithm:
모든 우선순위 큐 자료구조는 정렬 알고리즘으로 전환될 수 있습니다.
– build(A), e.g., insert items one by one in input order
입력 배열 A를 기반으로 입력 순서대로 하나씩 insert하여 build하여 우선순위 큐를 구성합니다.
– Repeatedly delete min() (or delete max()) to determine (reverse) sorted order
그 후, delete min() 또는 delete max()를 반복하여 정렬된 결과를 얻습니다.
delete min() → 오름차순 정렬
delete max() → 내림차순 정렬
• All the hard work happens inside the data structure
실질적인 복잡한 처리는 모두 우선순위 큐 내부에서 이루어집니다.
사용자는 단순히 삽입하고 삭제하기만 하면 됩니다.
• Running time is T_build + n · T_(delete_max) ≤ n · T_insert + n · T_delete_max
전체 시간 복잡도는 다음과 같습니다
- Tbuild: 큐를 만드는 데 걸리는 시간
- n · Tdelete max: n번 최댓값 삭제
대부분의 경우 build는 n · Tinsert보다 빠르므로,
최대 시간은 삽입 n번 + 삭제 n번에 해당하는 시간입니다.
• Many sorting algorithms we’ve seen can be viewed as priority queue sort:
우리가 배운 많은 정렬 알고리즘은 사실상 우선순위 큐 정렬의 일종으로 볼 수 있습니다.
힙 정렬(HeapSort)은 이 방식의 대표적인 예입니다.
시간 복잡도
3. Priority Queue: Set AVL Tree
• Set AVL trees support insert(x), find min(), find max(), delete_min(), and delete_max() in O(log n) time per operation
Set AVL 트리는 다음 연산들을 모두 O(log n) 시간에 처리할 수 있습니다:
- 삽입 (insert(x))
- 최소/최대값 찾기 (find min(), find max())
- 최소/최대값 삭제 (delete min(), delete max())
• So priority queue sort runs in O(n log n) time
따라서 우선순위 큐를 이용한 정렬은 전체적으로 O(n log n) 시간 복잡도를 가집니다.
– This is (essentially) AVL sort from Lecture 7
이는 사실상 강의 7에서 다룬 AVL 정렬과 동일한 방식입니다.
• Can speed up find min() and find max() to O(1) time via subtree augmentation
트리 노드에 하위 트리의 최소/최대값 정보를 추가하면
find_min()과 find_max() 연산을 O(1) 로 빠르게 만들 수 있습니다.
• But this data structure is complicated and resulting sort is not in-place
그러나 이 구조는 복잡하며, 정렬된 결과를 in-place (추가 메모리 없이) 만들지 못합니다.
즉, 별도의 트리 구조가 필요하므로 메모리를 더 사용합니다.
• Is there a simpler data structure for just priority queue, and in-place O(n lg n) sort?
그렇다면 우선순위 큐 기능만을 위해 더 단순하고, in-place 정렬이 가능한 구조는 없을까요?
YES, binary heap and heap sort
있습니다! 그것이 바로 바이너리 힙과 힙 정렬입니다.
• Essentially implement a Set data structure on top of a Sequence data structure (array), using what we learned about binary trees
바이너리 힙은 배열(Sequence) 위에 이진 트리 기반의 Set 자료구조를 구현한 것으로,
이진 트리에 대해 배운 내용을 활용하여 우선순위 큐 + 정렬을 동시에 수행할 수 있습니다.
4. Priority Queue: Array
• Store elements in an unordered dynamic array
정렬되지 않은 동적 배열에 요소들을 저장합니다. 순서 없이 추가만 합니다.
• insert(x): append x to end in amortized O(1) time
insert(x)는 x를 배열 끝에 추가합니다. 이 연산은 평균적으로 O(1) 시간에 수행됩니다.
• delete max(): find max in O(n), swap max to the end and remove
delete max()는 배열 전체를 O(n) 시간에 순회해서 최댓값을 찾고,
그 값을 배열 끝과 swap한 뒤 제거합니다.
• insert is quick, but delete_max is slow
삽입은 빠르지만, 삭제는 느립니다.
삽입: O(1)
삭제: O(n)
• Priority queue sort is selection sort! (plus some copying)
이 구현으로 만든 정렬 알고리즘은 선택 정렬(selection sort) 와 본질적으로 같습니다.
항목을 하나씩 선택해서 가장 큰 값을 뒤로 보내는 방식이 유사합니다.
(여기에 배열 복사 작업이 추가될 수 있음)
5. Priority Queue: Sorted Array
• Store elements in a sorted dynamic array
요소들을 항상 정렬된 상태로 유지하는 배열에 저장합니다.
• insert(x): append x to end, swap down to sorted position in O(n) time
insert(x) 시에는 일단 배열 끝에 추가한 후,
정렬된 위치로 앞쪽으로 스왑하면서 이동시킵니다.
이 과정은 최악의 경우 O(n) 시간 걸립니다.
• delete max(): delete from end in O(1) amortized
delete max()는 배열 끝에 있는 항목(최댓값)을 제거하므로 O(1) 시간에 빠르게 수행됩니다.
• delete max is quick, but insert is slow
삭제는 빠르지만, 삽입은 느립니다.
삭제: O(1)
삽입: O(n)
• Priority queue sort is insertion sort! (plus some copying)
이 구현으로 만든 정렬 알고리즘은 삽입 정렬(insertion sort) 와 유사합니다.
하나씩 삽입하며 정렬을 유지하기 때문입니다.
(정렬 결과를 얻기 위해 복사가 따를 수 있음)
• Can we find a compromise between these two array priority queue extremes?
그렇다면 삽입이 빠른 정렬되지 않은 배열과 삭제가 빠른 정렬된 배열이 두 가지 극단 사이의 절충안을 찾을 수 있을까요?
이 질문은 바이너리 힙과 힙 정렬로 이어지는 단서입니다.
6. Array as a Complete Binary Tree
• Idea: interpret an array as a complete binary tree, with maximum 2ᶦ nodes at depth i except at the largest depth, where all nodes are left-aligned.
아이디어는 배열을 완전 이진 트리로 간주하는 것입니다.
- 깊이 i에서는 최대 2^i 개의 노드가 있고
- 가장 마지막(최하단) 레벨에서는 왼쪽부터 차례대로 노드가 채워져 있습니다 (왼쪽 정렬).
• Equivalently, complete tree is filled densely in reading order: root to leaves, left to right
같은 말로 표현하면: 완전 이진 트리는 읽는 순서(위에서 아래, 왼쪽에서 오른쪽)로 빽빽하게 채워진 트리입니다.
• Perspective: bijection between arrays and complete binary trees.
이 관점에서는 배열과 완전 이진 트리 사이에는 일대일 대응(bijection) 이 존재합니다.
배열 하나당 완전 이진 트리를 만들 수 있고, 그 반대로도 가능합니다.
* bijection: 수학 용어로, 1:1 대응
• Height of complete tree perspective of array of n item is ⌊log n⌋, so balanced binary tree
n개의 원소를 가진 배열을 완전 이진 트리로 보면
트리의 높이는 ⌊log₂ n⌋ 이고, 이는 균형잡힌 이진 트리(balanced binary tree) 입니다.
즉, 각 연산을 효율적으로 수행할 수 있습니다.
7. Implicit Complete Tree
Implicit Complete Tree
포인터 없이 배열 인덱스만으로 완전 이진 트리를 표현하는 방식
* implicitly: 암시적으로
• Complete binary tree structure can be implicit instead of storing pointers
완전 이진 트리 구조는 포인터를 저장하지 않고도 배열 인덱스를 이용해 배열로 표현할 수 있습니다.
• Root is at index 0
트리의 루트 노드는 배열의 인덱스 0에 위치합니다
• Compute neighbors by index arithmetic:
트리에서의 자식/부모 노드 인덱스는 간단한 산술 계산으로 구할 수 있습니다:
- left(i) = 2i + 1
i번 인덱스의 왼쪽 자식은 2i + 1번 인덱스입니다. - right(i) = 2i + 2
i번 인덱스의 오른쪽 자식은 2i + 2번 인덱스입니다. - parent(i) = ⌊(i - 1) / 2⌋
i번 인덱스의 부모 노드는 (i - 1) / 2 (내림)한 인덱스입니다.
예시
| 인덱스(i) | left(i) = 2i+1 | right(i) = 2i+2 | parent(i) = ⌊(i-1)/2⌋ |
| 0 | 1 | 2 | - (루트라서 부모 없음) |
| 1 | 3 | 4 | 0 |
| 2 | 5 | 6 | 0 |
| 3 | 7 | 8 | 1 |
| 4 | 9 | 10 (X) | 1 |
| 5 | 11 (X) | 12 (X) | 2 |
| 6 | 13 (X) | 14 (X) | 2 |
| 7 | X | X | 3 |
| 8 | X | X | 3 |
| 9 | X | X | 4 |
이 방식은 포인터 없이 배열 하나로 트리를 표현할 수 있어 메모리 효율이 높아
힙(Heap) 같은 자료구조 구현에 자주 사용됩니다.
8. Binary Heaps
Binary Heaps: 특정 우선순위 조건을 만족하는 완전 이진 트리
• Idea: keep larger elements higher in tree, but only locally
핵심 아이디어: 큰 값이 트리 상단에 위치하도록 하되,
모든 노드에 대해 자식과의 관계만 고려합니다.
(전체 정렬이 아니라 로컬 정렬 조건만 유지)
• Max-Heap Property at node i: Q[i] ≥ Q[j] for j ∈ {left(i), right(i)}
맥스힙 트리에서 노드 i의 값은 자식 노드들 (left(i), right(i))보다 크거나 같아야 합니다.
• Max-heap is an array satisfying max-heap property at all nodes
맥스힙(max-heap)이란 배열의 모든 노드가 위의 Max-Heap 조건을 만족하는 구조입니다.
위로 올라갈 수록 값이 커지는 트리
• Claim: In a max-heap, every node i satisfies Q[i] ≥ Q[j] for all nodes j in subtree(i)
주장: 최대 힙에서는, 모든 노드 i는 자신의 서브트리 안에 있는 모든 노드 j보다 크거나 같습니다
• Proof:
– Induction on d = depth(j) − depth(i)
귀납법(induction)을 사용합니다.
d는 j가 i보다 얼마나 아래에 있는지를 나타내는 깊이 차이입니다.
1. Base Case
– Base case: d = 0 implies i = j implies Q[i] ≥ Q[j] (in fact, equal)
기초 단계: 깊이 차이 d = 0 이면 i = j
→ Q[i] ≥ Q[j] (동일하므로 성립)
2. Inductive Step
– depth(parent(j)) − depth(i) = d − 1 < d, so Q[i] ≥ Q[parent(j)] by induction
귀납 가정에 의해, i는 parent(j)보다 높기 때문에 Q[i] ≥ Q[parent(j)]입니다.
– Q[parent(j)] ≥ Q[j] by Max-Heap Property at parent(j)
그리고 Max-Heap 조건에 따라, parent(j)는 j보다 크거나 같습니다
Q[parent(j)] ≥ Q[j]
3. Conclusion
결론적으로:
Q[i] ≥ Q[parent(j)] ≥ Q[j] → 따라서 Q[i] ≥ Q[j] 성립
• In particular, max item is at root of max-heap
결론: 최대 힙에서 가장 큰 값은 항상 루트(최상단 노드) 에 있습니다.
→ 그래서 delete max()는 항상 루트를 제거하면 됩니다.
예시 Q[i] ≥ Q[j] 를 증명해 보자
1. Base Case
d = 0이면 i = j이므로 당연히 Q[i] ≥ Q[j] (같음)
예: i = 3, j = 3 → Q[3] = Q[3] = 30
2. Inductive Step
"d = 0, 1, ..., k까지는 성립한다고 가정하자"
그럼 d = k + 1에서도 성립하는지 증명해야 한다
우리는 Q[i] ≥ Q[j]를 직접 증명할 수 없으니, j의 부모(parent(j))를 먼저 생각해 봅니다.
왜냐하면 Q[i] ≥ Q[parent(j)] 는 더 짧은 깊이 차이를 가지니까
그건 이미 귀납 가정에 의해 성립한다고 볼 수 있습니다
i는 루트(0), j는 어떤 서브트리의 노드, 예를 들어 j = 6이라 합시다.
그럼 i = 0 이면 Q[0] = 90,
j = 6 이면 Q[6] = 50
depth(j) - depth(i) = d
- i = 0 (루트), → depth(i) = 0
- j = 6 → depth(j) = 2
따라서 d = depth(j) - depth(i) = 2 - 0 = 2
귀납 가정: Q[0] ≥ Q[2]
→ 맞음: 90 ≥ 80
Max-Heap Property at parent(6): Q[2] ≥ Q[6]
→ 맞음: 80 ≥ 50
3. 결론:
Q[0] ≥ Q[2] ≥ Q[6] → 따라서 Q[0] ≥ Q[6]
즉, 루트는 자신의 서브트리 어떤 노드보다도 값이 크다는 것이 귀납적으로 증명됩니다.
9. Heap Insert
• Append new item x to end of array in O(1) amortized, making it next leaf i in reading order
새로운 항목 x를 배열 끝에 추가합니다. 이 연산은 평균적으로 O(1) 시간에 수행됩니다.
이 항목은 읽는 순서(reading order) 기준으로 다음 잎 노드(i) 가 됩니다. (트리의 가장 아래 왼쪽부터 채워지는 구조)
• max heapify up(i): swap with parent until Max-Heap Property
Max-Heap 성질을 만족하도록 i번 노드를 위로 올리며 위치를 조정하는 과정 즉 max heapify up(i)을 한다
* heapify: 힙(Heap) 구조로 만드는 과정. 배열이나 트리 구조를 힙의 조건(Max-Heap 또는 Min-Heap 조건)을 만족하도록 재구성
– Check whether Q[parent(i)] ≥ Q[i] (part of Max-Heap Property at parent(i))
현재 노드 i와 그 부모 노드 parent(i)를 비교합니다.
Q[parent(i)] ≥ Q[i] 이면 힙 속성 유지 → 종료.
– If not, swap items Q[i] and Q[parent(i)], and recursively max heapify up(parent(i))
만약 부모보다 크면, Q[i]와 Q[parent(i)]를 스왑한 후,
부모 쪽으로 계속 올라가며 재귀적으로 max heapify up을 수행합니다.
• Correctness: 왜 이게 항상 맞는가?
– Max-Heap Property guarantees all nodes ≥ descendants, except Q[i] might be > some of its ancestors (unless i is the root, so we’re done)
처음에 삽입한 Q[i]는 부모가 자기보다 작다면 자기가 올라가고 부모를 내린다 (루트라면 이미 끝)
– If swap necessary, same guarantee is true with Q[parent(i)] instead of Q[i]
만약 스왑이 일어난다면, 새 위치에서도 같은 작업 반복합니다
• Running time: height of tree, so Θ(log n)!
이 연산은 트리의 높이만큼만 반복되므로 최악의 경우 시간 복잡도는 Θ(log n) 입니다.
완전 이진 트리는 항상 균형 잡혀 있기 때문입니다.
10. Heap Delete Max
Heap Delete Max
최대 힙에서 최댓값을 삭제하는 연산입니다.
Max-Heap에서는 최댓값이 항상 루트(맨 위)에 있으므로, 루트 노드를 제거하고 힙 속성을 유지하도록 재정렬합니다
• Can only easily remove last element from dynamic array, but max key is in root of tree
동적 배열(힙 구현 방식)에서는 마지막 원소를 제거하는 것이 가장 쉽지만, 최대 힙에서 최댓값은 배열의 첫 번째(루트) 원소입니다.
따라서 바로 삭제할 수 없습니다.
• So swap item at root node i = 0 with last item at node n − 1 in heap array
그래서 배열의 첫 번째 원소(루트, index 0)와 마지막 원소(index n-1)를 바꿉니다.
그러면 최댓값이 배열 끝으로 가게 됩니다.
• max heapify down(i): swap root with larger child until Max-Heap Property
그 후 루트에 있는 원소가 힙 속성을 만족하도록 아래로 내려가며 자식 노드와 교환하는 max heapify down(i) 과정을 실행합니다.
이 과정은 자식 중 더 큰 값과 계속 바꾸며 내려갑니다.
– Check whether Q[i] ≥ Q[j] for j ∈ {left(i),right(i)} (Max-Heap Property at i)
즉, 현재 노드 Q[i]가 두 자식 중 큰 것보다 크거나 같은지 확인합니다. 이것이 Max-Heap Property 입니다.
– If not, swap Q[i] with Q[j] for child j ∈ {left(i),right(i)} with maximum key, and recursively max heapify down(j)
만약 Q[i]가 더 작다면, 두 자식 중 더 큰 값 Q[j]와 swap하고, j 위치에서 다시 재귀적으로 max heapify down(j)을 실행합니다.
• Correctness:
이제 이 알고리즘이 왜 참인지 설명하겠습니다.
– Max-Heap Property guarantees all nodes ≥ descendants, except Q[i] might be < some descendants (unless i is a leaf, so we’re done)
Max-Heap에서는 모든 노드가 자식보다 크거나 같지만, Q[i]는 위에서 swap되어 내려왔기 때문에 일시적으로 힙 속성을 깨고 있을 수 있음. 다만 i가 리프 노드면 더 이상 비교할 필요가 없으므로 끝입니다.
– If swap is necessary, same guarantee is true with Q[j] instead of Q[i]
만약 Q[i]와 자식 Q[j]를 바꾸면, 이제 Q[j]가 위로 올라왔기 때문에 동일한 조건(자식보다 클 것)을 다시 검증해야 합니다. 그래서 계속 재귀적으로 확인합니다.
• Running time: height of tree, so Θ(log n)!
이 연산은 힙 트리의 높이만큼만 수행되므로, 시간 복잡도는 Θ(log n) 입니다.
이진 트리의 높이는 log n이기 때문입니다.
11. Heap Sort
Heap Sort
Heap 자료구조, 특히 max-heap을 우선순위 큐에 연결하면 정렬 알고리즘으로 사용할 수 있습니다.
이를 Heap Sort라고 합니다.
• Plugging max-heap into priority queue sort gives us a new sorting algorithm
Max-heap을 우선순위 큐로 사용하면 새로운 정렬 알고리즘을 만들 수 있습니다.
원소들을 힙에 삽입한 후, 최댓값을 하나씩 꺼내면서 정렬하는 방식입니다.
• Running time is O(n log n) because each insert and delete max takes O(log n)
삽입 연산(insert)과 최댓값 제거(delete max)는 각각 O(log n) 시간이 걸리고,
총 n개의 원소에 대해 이 연산을 하므로 전체 시간 복잡도는 O(n log n) 입니다.
• But often include two improvements to this sorting algorithm:
하지만 Heap Sort를 구현할 때는 보통 두 가지 개선을 적용해서 성능이나 메모리 사용을 더 최적화합니다.
12. In-place Priority Queue Sort
In-place Priority Queue Sort
메모리를 추가로 쓰지 않고, 배열 안에서 직접 정렬하는 방식으로 우선순위 큐 정렬을 구현하는 방법입니다.
- 삽입(insert)과 삭제(delete max)는 모두 배열 A 안의 인덱스를 바꿔가며 작업합니다.
- 정렬된 값(최댓값)은 A 배열의 뒤쪽에 차곡차곡 쌓이며, 기존 힙 영역(|Q|)은 점점 줄어듭니다.
- 별도의 배열을 새로 만들지 않고, 오직 배열 A 하나만 사용
• Max-heap Q is a prefix of a larger array A, remember how many items |Q| belong to heap
Max-heap Q는 배열 A의 앞부분 일부(prefix) 로 사용됩니다.
이때, 현재 몇 개의 항목이 힙에 속해 있는지를 |Q|로 기억합니다.
in-place heap sort에서는 배열 전체 A를 두 부분으로 나눠서 사용합니다
- A[0] ~ A[ |Q| - 1]: 현재 힙으로 사용 중인 영역
- A[ |Q| ] ~ A[ n-1 ]: 이미 정렬된 영역
따라서
* |Q|: 힙 연산(삽입/삭제)의 경계 표시자로 쓰이는 중요한 변수
• |Q| is initially zero, eventually |A| (after inserts), then zero again (after deletes)
초기에는 힙이 비어 있으므로 |Q| = 0입니다.
모든 항목을 힙에 삽입한 후에는 |Q| = |A| (전체 배열 크기)이고,
모든 항목을 꺼내면 다시 |Q| = 0이 됩니다.
• insert() absorbs next item in array at index |Q| into heap
삽입 연산은 배열의 다음 원소(인덱스 |Q|)를 힙에 흡수하면서 |Q|를 증가시킵니다.
즉, 힙을 점점 확장해 나가는 구조입니다.
• delete max() moves max item to end, then abandons it by decrementing |Q|
최댓값 제거 연산은 힙의 루트(최댓값)를 배열 끝으로 이동시킨 후 거기서 버린 것처럼 처리하며 |Q|를 감소시킵니다.
힙 영역은 줄어들고, 정렬된 영역은 배열 뒤쪽에 차곡차곡 쌓입니다.
• In-place priority queue sort with Array is exactly Selection Sort
만약 힙 대신 단순한 배열(선형 탐색으로 max 찾기)을 사용하면, 이 방식은 정확히 선택 정렬과 동일합니다.
• In-place priority queue sort with Sorted Array is exactly Insertion Sort
만약 정렬된 배열을 유지하면서 새로운 항목을 삽입하면, 이건 삽입 정렬(Insertion Sort)과 동일합니다.
• In-place priority queue sort with binary Max Heap is Heap Sort
그리고 이 방식에서 이진 최대 힙(binary max-heap) 을 사용할 경우, Heap Sort가 됩니다.
즉, 같은 기본 원리지만 자료구조에 따라 다른 정렬 알고리즘이 되는 것입니다.
예시
배열 A = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]로 in-place Heap Sort 동작을 예시로 설명해드릴게요.
초기 상태
- 배열 A = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
- 현재 힙에 들어간 항목 수 |Q| = 0
1단계: insert() — 힙을 만들기
각 insert()에서 A의 다음 원소를 힙의 끝에 추가하고 heapify up 합니다.
각 삽입은 A[|Q|]를 힙에 추가하는 방식입니다.
A = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 를 순서대로 힙에 삽입하면:
- insert(0) → [0]
- insert(1) → [1, 0]
- insert(2) → [2, 0, 1]
- ...
- 최종 힙 상태: [9, 8, 6, 7, 3, 5, 2, 0, 4, 1] (Max-Heap)
- 이때 |Q| = 10, 전체 배열이 힙이 됨.
2단계: delete max() — 정렬 시작
최댓값은 항상 루트(A[0])에 있으므로, 이것을 배열의 뒤쪽(A[|Q|-1])으로 swap 한 뒤,
힙 크기 |Q|를 줄이고, 루트에서 heapify down을 수행합니다.
delete max():
- 루트 9 ↔ 마지막 1 → [1, 8, 6, 7, 3, 5, 2, 0, 4, 9]
- heapify down 후 → [8, 7, 6, 4, 3, 5, 2, 0, 1, 9]
- |Q| = 9
- delete max():
- 8 ↔ 1 → [1, 7, 6, 4, 3, 5, 2, 0, 8, 9]
- heapify down 후 → [7, 4, 6, 1, 3, 5, 2, 0, 8, 9]
- |Q| = 8
- 반복적으로 수행하면:
→ 최종 배열: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
정렬 완료!!
13. Linear Build Heap
• Inserting n items into heap calls max_heapify_up(i) for i from 0 to n − 1 (root down):
n개의 항목을 heap에 순차적으로 insert() 한다면, 각 삽입마다 heapify up이 발생하며,
i = 0부터 n - 1까지 실행됩니다. (즉, 루트부터 아래로 원소를 쌓아가며 위로 heapify)
이 삽입 방식에서 발생하는 최악의 경우 swap 횟수 총합은 각 노드의 깊이(depth)에 비례합니다.
- 루트에 가까운 노드는 적은 swap, 아래쪽 노드는 많은 swap 필요
- 총합을 계산하면 depth(0) + depth(1) + ... + depth(n-1) ≈ log(n!)
- Stirling 근사를 사용하면 lg(n!) ≥ (n/2) * lg(n/2)
→ 결과적으로 시간 복잡도는 Ω(n log n)
• Idea! Treat full array as a complete binary tree from start, then max_heapify_down(i) for i from n − 1 to 0 (leaves up):
개선된 아이디어는 다음과 같습니다. 배열을 처음부터 완전 이진 트리 구조로 간주하고,
i = n−1에서 0까지 아래에서 위로, 각 노드에 대해 max_heapify_down(i)을 실행합니다.
→ 삽입 없이 힙을 한 번에 구성하는 방식입니다.
이번에는 각 노드가 아래로 내려갈 수 있는 높이(height(i))를 기준으로 swap을 계산합니다.
높은 곳(i가 작음)에 있는 노드는 많이 heapify down 할 수 있고,
아래쪽(i가 큼)은 거의 하지 않습니다.
log n − log i?
i번째 노드에서 아래로 heapify할 때 최대 깊이는
log₂ n (트리 높이)에서 현재 노드 깊이인 log₂ i를 뺀 것
→ height(i) = log₂ n − log₂ i = log₂(n / i)
≈ Θ(n)
총합을 계산하면 Θ(n) 정도의 작업만 필요합니다.
이 때문에 이 방식은 전체 힙 구성(build heap)을 선형 시간(O(n))에 끝낼 수 있습니다.
• So can build heap in O(n) time
결론: 이 방식으로 하면 삽입 없이 힙을 구성할 수 있으며, 시간 복잡도는 O(n) 입니다.
• (Doesn’t speed up O(n lg n) performance of heap sort)
단, Heap Sort 전체 알고리즘의 시간 복잡도는 여전히 O(n log n) 입니다.
왜냐하면 힙을 구성한 뒤에도, 정렬을 위해 n번 delete max (heapify down) 를 해야 하기 때문입니다.
→ build heap만 빨라졌을 뿐, 정렬은 log n씩 n번 = O(n log n)
14. Sequence AVL Tree Priority Queue
Sequence AVL Tree Priority Queue
우선순위 큐를 구현하는 새로운 방법
• Where else have we seen linear build time for an otherwise logarithmic data structure? Sequence AVL Tree!
보통 로그 시간(예: O(log n))에 작동하는 자료구조에서, 구축(build) 시간은 O(n log n)이 걸립니다.
그런데 Sequence AVL Tree는 O(n)이라는 선형 시간에 구축이 가능합니다.
→ 마치 힙(heap)도 O(n) 시간에 build 가능한 것처럼요.
• Store items of priority queue in Sequence AVL Tree in arbitrary order (insertion order)
우선순위 큐의 데이터를 Sequence AVL Tree에 임의의 순서(즉, 삽입 순서)로 저장합니다.
꼭 정렬된 상태일 필요는 없습니다.
• Maintain max (and/or min) augmentation:
각 노드에 최댓값(또는 최솟값)을 가리키는 포인터 정보를 유지시킵니다.
즉, 그 노드가 루트인 서브트리 안에서 가장 큰 값을 갖는 노드를 가리킵니다.
node.max = pointer to node in subtree of node with maximum key
이처럼 node.max는 해당 서브트리에서 가장 큰 key를 가진 노드를 가리킵니다.
– This is a subtree property, so constant factor overhead to maintain
이 max 값은 서브트리 정보이므로, 삽입/삭제 시 O(1) 추가 작업으로 쉽게 유지할 수 있습니다.
즉, 리밸런싱 중에도 같이 업데이트하면 됩니다.
• find min() and find max() in O(1) time
이렇게 max/min 포인터를 유지하므로, 최댓값/최솟값 찾기는 O(1)에 가능합니다.
• delete min() and delete max() in O(log n) time
하지만 실제 삭제는 AVL 트리의 구조를 변경해야 하므로, O(log n)의 시간이 필요합니다.
AVL 트리의 높이만큼 재조정해야 하기 때문입니다.
• build(A) in O(n) time
초기 배열 A를 기반으로 AVL 트리를 구성할 때는 O(n)의 선형 시간에 가능합니다.
이건 build를 균형 잡힌 방식으로 할 경우 (예: sorted array → AVL tree) 가능합니다.
• Same bounds as binary heaps (and more)
결과적으로 시간 복잡도는 이진 힙(binary heap)과 동일하지만,
그보다 더 많은 연산을 지원합니다 (예: 중간 삽입, 순서 유지 등).
즉, 우선순위 큐 이상의 기능을 갖춘 자료구조입니다.
15. Set vs. Multiset
Set(집합)과 Multiset(중복 허용 집합)의 차이와, Set을 기반으로 Multiset을 어떻게 구현할 수 있는지 알아봅시다
• While our Set interface assumes no duplicate keys, we can use these Sets to implement Multisets that allow items with duplicate keys:
Set은 중복된 키를 허용하지 않는 것이 기본입니다.
그러나 약간의 아이디어를 추가하면 중복 키를 허용하는 Multiset을 구현할 수 있습니다.
– Each item in the Set is a Sequence (e.g., linked list) storing the Multiset items with the same key, which is the key of the Sequence
구체적으로는, Set 안에 각 키마다 하나의 Sequence(예: 연결 리스트)를 저장하는 방식입니다.
- Set의 키는 각 그룹의 공통 키
- 그 키에 해당하는 값들은 해당 Sequence에 저장 (중복 허용)
예시:
Set:
{
5 → [item1, item2],
7 → [item3],
9 → [item4, item5, item6]
}
위 구조는 키 5, 7, 9를 가지는 Multiset을 의미하며, 키가 같은 항목들이 리스트로 모여 있습니다.
• In fact, without this reduction, binary heaps and AVL trees work directly for duplicate-key items (where e.g. delete_max deletes some item of maximum key), taking care to use ≤ constraints (instead of < in Set AVL Trees)
사실 위와 같은 방식으로 바꾸지 않아도, 중복 키 사용이 가능한 이진 힙이나 AVL 트리를 사용하면 된다
AVL 트리는 노드 정렬을 위해 비교 연산자를 사용하므로,
Set에서는 중복을 막기 위해 < 조건만 썼지만,
Multiset에서는 ≤를 써서 중복된 키도 들어갈 수 있게 한다
* Multiset: 중복 허용
* reduction: 문제를 다른 구조나 표현으로 바꾸는 것
* without this reduction - 앞에서 설명한 (Set의 항목을 리스트로 묶는) 변환(reduction) 없이도, 굳이 "Set of lists"처럼 구현하지 않아도
* constraint: 비교조건, 제약조건, <=을 사용해라
* delete_max deletes some item of maximum key: 최대 키를 가진 항목이 여러 개 있어도, 그 중 아무거나 하나만 삭제하면 된다는 것을 의미. 고로 중복 키 허용 구조임을 전제로 한다.
① 중복 키가 허용되지 않는 Set이라면?
- 예: {3, 5, 7}
- 키가 하나밖에 없기 때문에, delete max는 7 하나만 존재.
- 삭제하면 트리에서 해당 노드 하나만 빠짐.
- 중복 키 자체가 존재하지 않음 → 이런 상황은 delete max가 항상 단 하나의 노드를 다루게 됨.
② 중복 키가 허용되는 Multiset이라면?
- 예: {3, 5, 7, 7, 7}
- 이 경우 최대 키인 7이 여러 개 존재.
- delete max는 이들 중 "하나만 삭제하면 충분".
- 어떤 7이 삭제되는지는 중요하지 않음.
- 중요한 건 결과적으로 최대 키를 하나 제거하는 것.
→ 따라서 delete max 연산이 중복된 키 중 아무거나 하나만 삭제해도 된다는 말은,
그 구조가 중복 키를 허용해야 한다는 전제를 내포하고 있습니다.
요약
- 힙이나 AVL 트리는 중복 키를 직접 다룰 수 있다.
- 중복을 허용하려면 특별한 변환 없이도 구현 가능하다.
- 단, AVL 트리에서는 비교 연산을 <에서 ≤로 바꾸는 것이 필요하다.
- 그래서 delete max는 최댓값을 가진 것 중 아무거나 하나만 삭제해도 된다.
출처
https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/mit6_006s20_lec8/
Lecture 8: Binary Heaps | Introduction to Algorithms | Electrical Engineering and Computer Science | MIT OpenCourseWare
MIT OpenCourseWare is a web based publication of virtually all MIT course content. OCW is open and available to the world and is a permanent MIT activity
ocw.mit.edu
참고 자료
https://youtu.be/AjFlp951nz0?si=2fuAMdaiWrlEHDKf