[PS] Heap

Heap 개념

Heap은 Priority Queue로 구현하는 방식이다.
PQ : 우선순위부터 꺼내는 트리구조

Heap 조건

조건 1 : Perfect Binary Tree

1. Perfect : 노드의 순서가 위쪽 왼쪽 순
2. Binary : 자식이 최대 2개
3. Tree : CYCLE이 없는 그래프

조건 2 : 어떤 Node에서 직접 연결된 Node간의 우선순위가 알맞게 연결된 트리

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