[STL] make_heap
우선순위 큐를 구현하는데 가장 효과적인 자료구조는 힙 자료구조이다!
c++ STL 또한 priority_queue는 make_heap 기반으로 구현되어 있다.
힙 key point!)
1.
완전 이진 트리 구조를 갖는다. (이는 배열을 통한 구현이 가장 효율적이다)
2.
부모 노드는 자식 노드보다 우선순위가 높다 (자식 간에는 관계가 없다)
최대 힙, 최소 힙은 그저 값이 큰 데이터를 우선순위 있게 평가하느냐 그 반대이느냐 일 뿐이다.
구조적으로 힙은 배열을 이용하여 구현하는 것이 가장 빠르며, heap 관련 STL 또한 vector를 인자로 사용한다.
make_heap
c++ heap의 헤더파일은 <algorithm>에 정의되어 있다.
실제로 STL에서도, make_heap은 힙이라는 Container를 제공해 주는 것이 아니라, 사용자의 vector를 인자로 받아 힙 구조로 변환시켜 준다.
한번 해당 함수를 사용해 힙 구조를 구성하면, 새로운 데이터의 삽입과 삭제를 위해 push_heap, pop_heap을 동반해서 사용해야 빠르다 (각각 O(logN) 시간복잡도를 갖을 것임)
vector를 make_heap을 통해 힙을 구성하면, 우선순위가 가장 높은 데이터는 첫 번째 index에 위치하게 된다. 그리고 나머지 요소는 heap에 맞는 구조를 띄게 된다.
make_heap은 데이터의 우선순위를 재정의 해주지 않으면, 기본적으로 max_heap으로 구성된다.
예제)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(vector<int>& vs);
int main() {
vector<int> v(vector<int> { 1, 6, 5, 2, 3, 8, 4, 9, 7 });
cout << "before make_heap V : ";
print(v);
cout << "after make_heap V : ";
make_heap(v.begin(), v.end());
print(v);
return 0;
}
void print(vector<int>& vs) {
for (auto v : vs) {
cout << v << ' ';
}
cout << '\n';
}
// OUTPUT
// before make_heap V : 1 6 5 2 3 8 4 9 7
// after make_heap V : 9 7 8 6 3 5 4 2 1
C++
복사
make_heap 요약
vector를 heap 아키텍쳐로 재구성하며, 가장 우선순위가 높은 값은 vector의 맨 앞 인덱스에 위치해 있다.
추가)
임의의 순서를 갖는 배열이 주어질 때, heap 구조를 형성하는데 소요되는 시간복잡도는 O(N) 이다.
이는 직관에 의해 O(NlogN)으로 여겨질 수 있지만,
이는 Sift Down을 이용한 최적화를 통해 O(N)으로 힙을 형성할 수 있다.
Heap Method
push_heap
•
make_heap을 통해 heap 구조를 갖는 vector에 데이터 삽입을 원할 때 사용한다.
•
vector 아키텍쳐에 데이터를 삽입할 때는, 뒷 부분에 삽입해야하며, 제공되는 함수도 push_back(), emplace_back() 를 제공한다.
•
앞 부분에 삽입하면 O(N)의 시간복잡도를 갖고, 뒷부분에 삽입해야 O(1)의 시간복잡도를 가진다.
•
heap은 vector의 이러한 성질을 고려하여 push_heap이 설계된 듯 하다.
•
vector를 사용하여 make_heap을 형성했을 경우, push_heap은 vector의 데이터 삽입 이후에 사용되어야만 될 것이다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(vector<int>& vs);
int main() {
vector<int> v( vector<int> { 1, 6, 5, 2, 3, 8, 4, 9, 7 } );
make_heap(v.begin(), v.end());
v.push_back(10);
push_heap(v.begin(), v.end());
// push_back을 사용한 다면, 힙을 재구성하기 위해서 push_heap을 사용
print(v);
}
void print(vector<int>& vs) {
for (auto v : vs) {
cout << v << ' ';
}
cout << '\n';
}
// OUTPUT
// 10 9 8 6 7 5 4 2 1 3
C++
복사
실행 결과, 가장 우선순위가 높은 10이 맨 앞의 인덱스에 위치해 있고, 재배열 됨을 확인할 수 있다.
이는 비교 연산에 의해, O(logN)의 시간복잡도를 갖는다.
우리가 알고있는, 힙 아키텍쳐에 데이터 삽입 후, 비교 연산을 통해 아키텍쳐를 재구성 했음을 알 수 있다.
•
요약 : push_heap은 push_back() 또는 emplace_back()과 같이 사용할 수 밖에 없다.
pop_heap
•
힙의 삭제 연산이 수행될 것이며 O(logN)이 소요된다.
•
pop_heap은 우선순위가 가장 높은 값을 vector의 마지막 인자로 위치시키고, Heap 아키텍쳐를 재배열한다.
•
이때, 맨 마지막 인자는 힙 아키텍쳐에 포함시키지 않은 상태의 재배열을 수행한다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(vector<int>& vs);
int main() {
vector<int> v( vector<int> { 1, 6, 5, 2, 3, 8, 4, 9, 7 } );
make_heap(v.begin(), v.end());
cout << "before pop : ";
print(v);
pop_heap(v.begin(), v.end());
cout << "after pop : ";
print(v);
v.pop_back();
// pop_heap을 하면 빼야하는 수가 맨 뒤로 오게 되고, pop_back()을 하면 그 수를 지울 수 있다.
return 0;
}
void print(vector<int>& vs) {
for (auto v : vs) {
cout << v << ' ';
}
cout << '\n';
}
C++
복사
만약 Min Heap으로 구성하고 싶으면?
제일 간단한 방법! (우선순위 큐 STL 사용하기)
priority_queue<int, vector<int>, greater<int>> pq;
C++
복사
sort_heap
c++ STL에서는 sort_heap 함수도 제공해 주는데, 힙 구조인 vector를 정렬 시켜준다.
시간복잡도는 O(NlogN)으로 sort와 같다.
STL의 정렬 알고리즘 sort는 Quick Sort를 기반으로 구현되어 있는데,
이미 힙 구조를 띄는 vector는 sort_heap을 사용하는 것 보다 sort 함수를 사용한 것이 더 빠르다.
•
sort_heap 대신 그냥 sort()가 더 빠르다.
데이터 우선순위 지정
comp 인자 이해하기
heap을 생성할 때, 연산자를 지정해주지 않으면, default하게 data의 값이 큰 값이 높은 우선순위를 갖도록 하는 max heap 아키텍쳐를 구성하게 된다.
이를 사용자가 재정의 하기 위해서는 비교 연산자를 정의하여 인자로 넘겨주면 된다.
비교 연산자는, 다른 요소와 비교할 때, false를 리턴하는 값이 가장 우선순위가 높다.