[Algorithm] 23 우선순위 큐와 힙 - 2
최대 원소 꺼내기
배열을 이용해 구현한 최대 힙에서 최대 원소 찾기 : 배열의 첫 원소를 찾으면 된다.
하지만, 최대 원소를 힙에서 꺼내는 것은 루트를 지우는 작업이고, 모양 제한이 있어 까다롭다.
새 원소의 삽입에서 그랬던 것 처럼 모양 규칙을 충족하는 힙을 만든 뒤, 대소 관계 규칙을 만족하도록 하면 어떨까?
최대 원소를 꺼내고자 할 때
- 힙의 모양 구조에 따라 힙의 마지막 노드는 어차피 지워질 것이므로 먼저 지운다.
- 위에서 지운 노드에 있던 원소를 루트에 덮어 씌운다.
이제 모양 규칙은 만족시켰으므로 원소의 대소 관계 조건만 만족시키면 된다.
트리의 바닥에 도달하거나, 두 자손이 모두 자기 자신의 이하의 원소를 갖고 있을때 까지
두 자식 노드가 가진 원소 중 더 큰 원소를 선택해 루트가 갖고 있는 원소와 바꾼다. (반복)
while 문 실행 마다 트리의 아래 레벨로 내려가기 때문에 복잡도는 O(logN)
// 정수를 담는 최대 힙 heap 에서 heap[0]을 제거한다.
void pop_heap(vector<int>& heap) {
// 힙의 맨 끝에서 값을 가져와 루트에 덮어씌운다.
heap[0] = heap.back();
heap.pop_back();
int here = 0;
while(true) {
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;
}
}
다른 연산들
- 힙을 만드는 연산 O(N)
- N 개의 원소를 텅 빈 힙에 순서대로 삽입해야 할 때 사용
- 길이 N인 배열에 저장한 뒤, 힙을 만드는 연산을 수행
- 어차피 N개의 원소를 다시 꺼내는 데만도 O(NlongN) 의 시간이 걸려 큰 의미 없음
- 힙 정렬 (Heapsort)
- 힙에서 원소들을 꺼낼 때 항상 정렬된 순서로 반환된다는 점을 이용
- 주어진 배열을 힙으로 만든 뒤 모든 원소들을 꺼내서 반환 순서대로 배열
- 원소를 하나 꺼내면 힙 정렬 맨 뒤가 비므로, 최대 원소를 여기에 옮기면 추가 메모리 사용없이 정렬을 구현할 수 있다.
23.3 문제: 변화하는 중간 값
한 수열의 중간값(median)은 이 수열을 정렬했을 때 가운데 오는 값입니다.
예를 들어 {3,1,5,4,2}를 정렬했을 때 가운데 오는 값은 3이고, 수열의 길이가 짝수일 때는 가운데 있는 두 값 중 보다 작은 것을 수열의 중간값이라고 정의한다.
한 수열의 중간값은 수열에 새로운 수가 추가될 때마다 바뀔 수 있다.
텅 빈 수열에서 시작해서 각 수가 추가될 때마다 중간값을 계산하는 프로그램을 작성하세요.
예를 들어 3, 1, 5, 4, 2 순서대로 숫자가 추가될 경우 수열의 중간값은 3, 1, 3, 3, 3 순서로 변화합니다.
입력 생성
- A[0] = 1983
-
A[i] = (A[i-1] * a + b) % 20090711
a와 b는 입력에 주어지는 상수입니다.
10 1 0
A[0] = 1983
A[1] = (1983 * 1 + 0) mod 20090711 = 1983
A[2] = (1983 * 1 + 0) mod 20090711 = 1983
A[3] = (1983 * 1 + 0) mod 20090711 = 1983
A[4] = (1983 * 1 + 0) mod 20090711 = 1983
A[5] = (1983 * 1 + 0) mod 20090711 = 1983
A[6] = (1983 * 1 + 0) mod 20090711 = 1983
A[7] = (1983 * 1 + 0) mod 20090711 = 1983
A[8] = (1983 * 1 + 0) mod 20090711 = 1983
A[9] = (1983 * 1 + 0) mod 20090711 = 1983
=> 19830
10000 1273 4936
A[0] = 1983
A[1] = (1983 * 1273 + 4936) mod 20090711 = 2,529,295
| num | ordered | median |
|---|---|---|
| 3 | 3 | 3 |
| 1 | 1, 3 | 1 |
| 5 | 1, 3, 5 | 3 |
| 4 | 1, 3, 4, 5 | 3 |
| 2 | 1, 2, 3, 4, 5 | 2 |
---
1
2 5
3 4
---
출력
N 개의 중간 값의 합을 20090711 로 나눈 나머지를 출력