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

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

728x90

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 // Callable들을 보관할 수 있는 객체 #include #include 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, vector와 같은 Container, Compare 비교함수 클래스 //1. MaxHeap priority_queue, less> maxHeap; //2. MinHeap priority_queue, greater> minHeap; //3. 구현체를 직접 커스텀하는 경우 priority_queue, cmp> pq; pq.push(Custom(5)); cout << pq.top().value << ""; }

반응형

from http://6ro-29.tistory.com/31 by ccl(A) rewrite - 2021-12-27 03:01:21