[PS] Heap

Heapコンセプト

Heap優先キューで実現する方式です.PQ:優先度からポップアップするツリー構造

Heap条件

조건 1 : Perfect Binary Tree

Perfect:ノード順上から左へ

バイナリ:最大2児

Tree:CYCLEのないパターン

조건 2:直接接続ノード間の優先度に一致するツリー

Heap基本コード

#include <iostream>
#include <queue>
using namespace std;

int main() 
{
	// 우선순위 : 큰 값
	priority_queue<int> pq;

	pq.push(1);
	pq.push(5);
	pq.push(2);
	pq.push(7);
	pq.push(9);
	pq.push(6);
	pq.push(3);

	while (!pq.empty()) // pq가 비워졌다면 종료
	{
		int now = pq.top();
		pq.pop(); // 우선순위 높은것 삭제

		cout << now << " ";
	}
	

	return 0;
}

Heap構造の作成

heap削除構造

Heapアプリケーション:優先度の変更

優先度:小さい値

// 우선순위 : 작은 값
	priority_queue<int, vector<int>, greater<int>> pq;

に変更します.

構造優先度or多優先度

priority_queue<int> pq;のDefaultは<演算子です.そこで、優先度を与えるためにoperator<関数を作成します.

#include <iostream>
#include <queue>
using namespace std;

struct node
{
	int row;
	int col;
};

int operator<(node left, node right)
{	
	// true인 1을 반환하면 교환, false인 0을 반환하면 유지
	// row의 우선순위 : 작은순
	if (left.row > right.row) return 1;
	if (left.row < right.row) return 0;
	// col의 우선순위 : 큰 순
	if (left.col < right.row) return 1;
	if (left.col < right.col) return 0;

	return 0; 
}

int main() 
{
	priority_queue<node> nodePQ;

	nodePQ.push({1,5});
	nodePQ.push({2,9});
	nodePQ.push({5,3});
	nodePQ.push({5,7});

	while (!nodePQ.empty())
	{
		node now = nodePQ.top();
		nodePQ.pop(); // 우선순위 높은것 삭제

		cout << now.row << " " << now.col << endl;
	}
	

	return 0;
}