[C++] 우선순위 큐 STL(priority_queue)

With Heap Sort

Max heap, Min heap를 구현하기 위해서 사용하며, 계속해서 minimum 값을 구해야하는 다익스트라 알고리즘 같은 경우에서 priority_queue를 이용해 min heap을 사용하면 좀 더 짧은 시간에 해결할 수 있다.

 

Perfect Binary Tree(포화 이진 트리)

-> 말단 노드를 제외한 모든 노드의 차수가 2로 트리의 레벨마다 비어있는 공간이 존재하지 않음.

Complete Binary Tree(완전 이진 트리)

-> leaf node의 오른쪽 노드는 비어 있을 수 있으며 배열에 저장하는 것이 가장 효율적.

 

Heap은 Complete Binary Tree를 만족.

 

Max Heap : 부모 노드는 항상 자식 노드에 들어있는 값 보다 크다.

Min Heap : 부모 노드는 항상 자식 노드에 들어있는 값 보다 작다.

 

priority queue STL 사용 예시

#include<iostream>

// Callable들을 보관할 수 있는 객체
#include<functional>
#include<queue>
using namespace std;

struct Custom {
	int x;
	int y;
	int value;
	Custom(int value) : x(0), y(0), value(value) {}
};

//오름차순 정렬
struct cmp {
	bool operator()(Custom a, Custom b) {
		return a.value > b.value;
	}
};

int main() {

	// priority_queue<T, Container, Compare>
	// 원하는 자료형 및 클래스 T, vector와 같은 Container, Compare 비교함수 클래스
    
    	//1. MaxHeap
	priority_queue<int, vector<int>, less<int>> maxHeap;

	//2. MinHeap
	priority_queue<int, vector<int>, greater<int>> minHeap;

	//3. 구현체를 직접 커스텀하는 경우
	priority_queue<Custom, vector<Custom>, cmp> pq;

	pq.push(Custom(5));
	cout << pq.top().value << "";
}