힙은 컨테이너가 아니라 데이터를 구성하는 방식을 말한다. 힙이 무엇인지 이해하려면 트리에 대한 지식이 선행되어야 하나, 이 글에서는 넘어가겠다.
힙은 완전 이진 트리이고, 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
힙은 일종의 느슨한 정렬 상태를 유지하며, 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)
각 노드는 자식 노드에 따라 정렬된다. 힙의 종류에는 부모 노드가 항상 자식 노드보다 크거나 같아야 하는 최대 힙(max heap)이 있고, 부모 노드가 항상 자식 노드보다 작거나 같아야 하는 최소 힙(min heap)이 있다.
여기서 알고 가면 좋은 점은, priority_queue가 바로 힙이라는 점이다! priority_queue의 인스턴스는 내부에서 힙을 생성한다. 그렇다면 왜 C++ STL에서는 이미 힙인 priority_queue와 힙을 생성할 수 있는 두가지 기능이 있을까?
priority_queue는 원소 순서가 자동으로 관리된다는 점에서 장점이 있다. 우선순위 큐는 첫번째 원소만 접근할 수 있고 다른 원소에는 접근할 수 없으므로 priority_queue의 정렬된 상태를 망가뜨릴 수 없다. 원하는 자료구조의 형태가 우선순위 큐라면 이는 큰 장점이다.
하지만 make_heap()을 사용하여 힙을 생성하면 priority_queue에는 없는 몇 가지 장점이 있다.
1. 힙에서는 가장 큰 원소 뿐 아니라 어떤 원소에도 접근할 수 있다. 이 과정에서 원소들의 순서 일관성을 훼손할 수도 있지만 이는 make_heap()을 호출해서 언제든지 복구할 수 있다.
2. 랜덤 액세스 반복자를 지원하는 어떤 시퀸스 컨테이너로도 힙을 생성할 수 있다. (ex. 일반 배열, string 객체, 직접 정의한 컨테이너 등) 즉, 필요할 떄 순차열 컨테이너의 원소들을 힙으로 배열할 수 있고, 필요하다면 반복해서 힙으로 배열할 수 있다는 뜻이다.
3. 힙 순서를 유지하는 힙 함수를 사용한다면 힙을 우선순위 큐로 쓸 수 있다.
- push_heap() : 힙 배치를 유지하기 위해 순차열의 적절한 위치에 원소 삽입
- pop_heap() : 첫 번쨰 원소를 끝으로 보내고 끝으로 보낸 마지막 원소를 제외한 나머지 원소들로 힙을 만든다. 그 다음에 vector의 pop_back() 멤버를 호출해서 마지막 원소를 제거한다.
* 만약 make_heap()에 비교 함수를 지정해 힙을 생성했다면 pop_heap()의 세 번째 인수에도 같은 비교 함수를 지정해야 한다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <double> nums {2.5, 10.0, 3.5, 8.0, 12.0, 1.5, 6.0};
make_heap(begin(nums), end(nums), greater<>()); // 결과 : 1.5 6 2.5 6.5 8 12 3.5 10
pop_heap(begin(nums), end(nums), greater<>()); // 결과 : 2.5 6 3.5 6.5 8 12 10 3.5
nums.pop_back(); // 결과 : 2.5 6 3.5 6.5 8 12 10
- is_heap() : 지정된 범위가 힙이면 true 반환
1) 조건자 X 경우
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <double> nums {2.5, 10.0, 3.5, 8.0, 12.0, 1.5, 6.0};
make_heap(begin(nums), end(nums));
if(is_heap(begin(nums), end(nums)))
cout<< "it's still heap!" << endl;
else
cout<< "oh, we messed up the heap" << endl;
2) 조건자 greater<> 사용시
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <double> nums {2.5, 10.0, 3.5, 8.0, 12.0, 1.5, 6.0};
make_heap(begin(nums), end(nums),greater<>());
if(is_heap(begin(nums), end(nums), greater<>()))
cout<< "it's still heap!" << endl;
else
cout<< "oh, we messed up the heap" << endl;
- is_heap_until() : 범위에서 힙이 아닌 원소의 첫 번째 위치 반환
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <double> nums {2.5, 10.0, 3.5, 8.0, 12.0, 1.5, 6.0};
make_heap(begin(nums), end(nums). greater<>());
auto iter = is_heap_until(begin(nums), end(nums). greater<>());
if(iter != end(nums))
cout<< "numbers is a heap up to "<< *iter << endl;
여기서 주의해야 할 점은 전체 범위가 힙이라면 is_heap_until() 함수는 끝 반복자를 반환하게 되므로 if문에서는 끝 반복자를 역참조하지 않게 확인해줘야 한다. 또한, 지정된 범위가 원소 두 개 이하일 때도 끝 반복자를 반환한다. 매개변수 두 개를 쓰는 is_heap_until() 함수는 기본 조건자로 less<>를 사용한다.
- sort_heap() : 힙 범위 정렬 (만약 주어진 범위가 힙이 아니라면 런타임에 충돌함)
* 최대 힙을 정렬한 결과는 최소 힙이다. 즉, 힙 생성에 사용한 조건자가 greater<>였다면 최소 힙이 되고, sort_heap()을 실행한 결과는 원소들을 내림차순으로 정렬한 것이 된다. (최소 힙을 정렬한 결과는 최소 힙이 될 수 없다. )
다음은 최소 힙을 정렬한 결과는 최대 힙이 됨을 보여주는 코드이다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <double> nums {2.5, 10.0, 3.5, 8.0, 12.0, 1.5, 6.0};
make_heap(begin(nums), end(nums), greater<>()); // 결과 : 1.5 6 2.5 6.5 8 12 3.5 10
sort_heap(begin(nums), end(nums), greater<>()); // 결과 : 12 10 8 6.5 6 3.5 2.5 1.5
여기서 주목할 점은 algorithm 헤더에는 힙을 정렬할 수 있는 sort() 함수 템플릿이 정의되어 있는데, 왜 sort_heap() 함수가 있을까? sort_heap() 함수는 힙 정렬(Heap Sort)이라 불리는 특별한 정렬 함수를 사용한다. sort_heap() 함수는 힙을 만들고, 데이터가 부분적으로 정렬되어 있다는 사실을 이용해 데이터를 정렬한다. 힙의 부분 정렬을 이용하기 때문에 정렬을 더 빨리할 가능성이 있다! (물론 항상 그런 것은 아니다.)
사실 알고리즘 문제를 풀 때 힙 문제여도 순수하게 힙으로 구현하는 경우는 거의 없는 듯하다.... ㅎㅎ 대부분 priority_queue 써서 구현을 하는 것 같다 허허 이것도 문제를 풀어봐야 감이 느는 거겠지?
** 이 글은 C++14 STL 철저 입문 (아이버 호튼 저)에 기반하여 작성되었습니다 **
