Intro
- 우선순위 큐는 우선순위가 가장 높은 자료가 먼저 꺼내진다.
- 우선순위 큐는 이진검색트리로 구현할 수 있지만 heap으로 더 간단하게 구현할 수 있다.
- 힙을 사용하면 새 원소를 추가하는 연산과 가장 큰 원소를 꺼내는 연산을 모두 O(lgN)시간에 수행 할 수 있다.
힙의 정의와 구현
Heap
- 부모 노드가 가진원소는 항상 자식 노드가 가진 원소 이상이다. → 힙의 대소 관계 규칙
- 이진 검색 트리와는 달리 대소 관계 규칙은 부모와 자식 사이에만 적용 됨 (왼쪽 자식과 오른쪽 자식의 대소 관계를 규정하지 않음)
- 트리에서 가장 큰 원소는 항상 트리의 루트에 존재함
- 힙의 모양 규칙
- 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차야 한다.
- 마지막 레벨에 노드가 존재하면 가장 왼쪽부터 순서대로 채운다.
배열을 이용한 힙의 구현
- A[i]에 대응되는 노드의 왼쪽 자손은 A[2xi + 1]에 대응
- A[i]에 대응되는 노드의 오른쪽 자손은 A[2xi + 2]에 대응
- A[i]에 대응되는 노드의 부모는 A[(i-1)/2]에 대응
따라서 정수를 저장하는 힙은 다음과 같이 만들 수 있다.
1
vector<int> heap;
새 원소의 삽입
- 힙의 대소관계 규칙은 일단 무시하고, 모양 규칙 부터 만족한다. → 즉 heap[]의 가장 끝에 원소를 추가한다.
- 마지막에 추가한 새 원소를 자신의 부모 노드가 가진 원소와 비교하며 자리를 찾아간다.
정수 원소를 갖는 최대 힙에 새 원소 삽입하기
1
2
3
4
5
6
7
8
9
10
11
12
13
// 정수를 담는 최대 힙에 새 원소 newValue를 삽입한다.
void push_heap(vector<int>& heap, int newValue) {
// heap의 맨 끝에 newValue를 삽입한다
heap.push_back(newValue);
// 현재 newValue의 위치
int idx = heap.size() - 1;
// 루트에 도달하거나 newValue이상의 원소를 가진 조상을 만날 때 까지
while (idx > 0 && heap[(idx - 1) / 2] < heap[idx]) {
swap(heap[idx], heap[(idx - 1) / 2]);
idx = (idx - 1) / 2;
}
}
최대 원소 꺼내기
- 원소를 추가할 때와 마찬가지로 대소관계 규칙은 무시하고 모양규칙 부터 만족시킨다.
- 가장 뒤에 있는 원소를 루트 노드에 덮어 씌운다.
- 대소관계 규칙을 만족시킬 때 까지 원소를 swap 해준다.
정수 원소를 갖는 최대 힙에서 최대 원소 삭제하기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void pop_heap(vector<int>& heap) {
heap[0] = heap.back();
heap.pop_back();
int here = 0;
while (true) {
// 왼쪽 자식노드와 오른쪽 자식노드의 index
int left = here * 2 + 1, right = here * 2 + 2;
// 리프에 도달한 경우
if (left >= heap.size()) break;
// heap[here]이 내려갈 위치를 찾는다
int next = here;
if (heap[next] < heap[left]) next = left;
if (right < heap.size() && heap[next] < heap[right]) next = right;
if (next == here) break;
swap(heap[here], heap[next]);
here = next;
}
}
