개요
- #include <algorithm>에 정의
- make_heap은 사용자의 vector를 인자로 받아 힙 구조로 변환
- 새로운 데이터의 삽입과 삭제를 위해 push_heap, pop_heap 사용
make_heap
- vector를 max heap으로 구성
- make_heap(v.begin(),v.end(),greater<int>()); //최소힙
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(vector<int>& vs)
{
for (auto v : vs)
cout << v << ' ';
cout << endl;
}
int main() {
vector<int> v( vector<int> {1,6,5,2,3,8,4,9,7 });
cout << "Before make_heap V \\n";
print(v);
cout<<'\\n';
cout << "After make_heap V \\n";
make_heap(v.begin(), v.end());
print(v);
return 0;
}
push_heap
- push_heap(v.begin(),v.end(),greater<int>()); //오름차순
- heap 구조를 가지는 vector에 데이터를 삽입할 때 사용
- heap 형성 후, 데이터 삽입 이후에 사용
- 과정: 삽입 된 값은 가장 뒤에 삽입되며 부모노드와 비교를 통해 정렬된다.
#include <iostream> // std::cout
#include <vector> // std::vector
#include <algorithm>
using namespace std;
void print(vector<int>& vs)
{
for (auto v : vs)
cout << v << ' ';
cout << endl;
}
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);
//v.push_back(0);
push_heap(v.begin(),v.end());
print(v);
return 0;
}
pop_heap
- pop_heap(v.begin(),v.end(),greater<int>()); //오름차순
- pop_heap은 우선 순위가 가장 높은 값(max heap에서 가장 큰 값)을 vector의 마지막 인자로 위치시키고, 재배열
- pop 해줄 값을 맨 뒤로 보냈으니 pop_back을 통해 제거해야 함
- 과정: 제거해줄 값과 맨 뒤 값을 바꾸고 root 노드 값을 push_down하며 정렬해줌
#include <iostream> // std::cout
#include <vector> // std::vector
#include <algorithm>
using namespace std;
void print(vector<int>& vs)
{
for (auto v : vs)
cout << v << ' ';
cout << endl;
}
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();
return 0;
}