STL에는 자료구조 시간에 배우는 heap 연산 관련 알고리듬도 있습니다.
다음 내용은 'STL 튜토리얼·레퍼런스 가이드(STL Tutorial and Reference Guide, 2nd Edition)'
(Musser, Derge and Saini 著, 정승진 譯)에 나오는 내용입니다.
---------------------------------------------------------------------------------------
heap은 특정 원소를 선택하는 연산이나 정렬 연산을, 로그 시간 내에 수행할 수 있도록 구성되어 있는 특별한 시퀀스를 일컫는다. 두 개의 임의 접근 반복자로 구성된 구간 [first, last)가 다음 두 가지 조건을 만족시키면, 이 구간을 힙이라고 한다.
● 반복자 first가 가리키는 값은 구간에 속하는 원소들 중에서 가장 큰 값이다.
● 반복자 first가 가리키는 값은 pop_heap로 삭제하고, 새로운 원소를 추가할 때는 push_heap을 사용하며, 이 두가지 연산을 수행한 뒤에도 이 구간은 여전히 힙이 된다.
이 두가지 조건 때문에 힙을 우선순위 큐(priority queue)로 사용할 수 있다.
(인용자 註: 실제로 우선순위 큐의 기능만을 사용할 때는 priority_queue 컨테이너 어댑터를 사용하는 것이 편리합니다. 이 컨테이너 어댑터 내부의 코드가 이들 알고리듬을 호출하는 방식으로 되어 있습니다.)
■ heap 연산 알고리듬 4가지
● [first, last - 1) 이 힙일 때, push_heap은 [first, last)을 힙이 되도록 한다. 이 연산을 last - 1에 위치한 원소를 "힙에 푸시한다"라고 말한다.
● [first, last)가 힙일 때, pop_heap은 first에 위치한 값과 last - 1에 위치한 값을 서로 교환하여 [first, last - 1)가 힙이 되도록 한다. 이 연산을 first에 위치한 원소를 "힙에서 팝한다"라고 말한다.
● make_heap은 [first, last) 내의 원소들을 재배치하여 힙으로 구성한다.
● sort_heap은 힙인 구간 [first, last) 내의 원소들을 정렬한다.
■ 시간 복잡도
[first, last)의 사이즈를 N이라 하자. (N = last - first)
● push_heap과 pop_heap의 소요 시간은 O(log N)이다. push_heap은 최대 log N 번의 비교 연산을 수행하며, pop_heap은 최대 2 log N 번의 비교 연산을 수행한다.
● make_heap의 소요 시간은 O(N)이며, 최대 3N 번의 비교 연산을 수행한다.
● sort_heap의 소요 시간은 O(N log N)이며, 최대 N log N 번의 비교 연산을 수행한다.
--------------------------------------------------------------------------------------
이러한 heap 연산 알고리듬을 사용하여 정렬을 수행하려면, 위의 make_heap(first, last)과 sort_heap(first, last)을 차례로 사용하거나, partial_sort(first, last, last)를 사용하면 됩니다.)
힙 정렬은 퀵 정렬(quick sort) 알고리듬보다 상수배만큼 소요시간이 더 걸리지만, 항상 힙 크기만큼의 고정된 메모리만을 사용한다는 장점이 있습니다. 그래서 STLport에 사용된 sort 알고리듬은, 이러한 퀵 정렬과 힙 정렬을 절충한 introsort 라는 알고리듬을 사용합니다. 퀵 정렬을 사용하다가 bad partition이 많이 발생하는 나쁜 상황에서는 heap 정렬로 전환하는 방식입니다.)
---------------------------------------------------------------------------------------
다음은 push_heap과 pop_heap, make_heap과 sort_heap을 사용하여 정렬을 하는 예제입니다.
//---------------------------------------------------------------------------------------
// Illustrating the generic heap operations
//---------------------------------------------------------------------------------------
#include <cassert>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
// Initialize a vector of integers:
vector<int> vector1(5);
iota(vector1.begin(), vector1.end(), 0);
random_shuffle(vector1.begin(), vector1.end());
// Sort vector1 using push_heap and pop_heap:
for (i = 2; i < 5; ++i)
push_heap(vector1.begin(), vector1.begin() + i);
for (i = 5; i >= 2; --i)
pop_heap(vector1.begin(), vector1.begin() + i);
// Verify that the array is sorted:
for (i = 0; i < 5; ++i)
assert (vector1[i] == i);
// Shuffle the elements again:
random_shuffle(vector1.begin(), vector1.end());
// Sort vector1 using make_heap and sort_heap:
make_heap(vector1.begin(), vector1.end());
sort_heap(vector1.begin(), vector1.end());
// Verify that the array is sorted:
for (i = 0; i < 5; ++i)
assert (vector1[i] == i);
return 0;
}
