개요

• #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;
}