priority_queue

우선 순위 큐 priority_queue는 queue와 비슷하지만, 각 요소가 우선순위를 가지며 우선순위가 높은 요소가 먼저 처리되는 자료구조이다. 일반적인 FIFO(First Int First Out) 구조의 queue와는 다르게, 요소의 우선순위에 따라 정렬된 순서로 처리된다.
삽입/삭제는 항상 o(long n) 이고, top() 가장 높은 우선순위 원소 조회는 o(1) 이다.
그래서 가장 큰/작은 원소를 순식간에 추출해야하는 문제에 최적이다.

 

특징

1. 정렬된 상태 유지:

• 삽입되는 모든 요소는 우선 순위에 따라 자동으로 정렬된다.
• 높은 우선순위의 요소는 큐의 앞쪽에 위치한다.

2. 빠른 접근:

• 우선순위를 통해 최대 값 혹은 최소 값을 빠르게 가져올 수 있다.

3. Heap 기반 구현:

• 보통 Max-Heap 혹은 Min-Heap으로 구현된다.
• 삽입 및 삭제 연산은 O(log n)의 시작 복잡도를 가진다.

 

#include <queue>

// Max-Heap 선언
// 기본적으로 Max-Heap으로 동작한다.
// 우선순위 큐는 내부적으로 백터를 이용해서 생략을 해도 되지만, 
// 세 번째 인자를 넣기 위해선 명시적으로 써주어야한다.
priority_queue<int> == priority_queue<int, vector<int>, less<int>> MaxHeap;

// Min-Heap 선언
priority_queue<int, vector<int>, greater<int>> MinHeap;

// 커스텀 우선 순위
struct Node
{
	int Num;
    char Name;
    bool operator<(const Node& Other) const
    {
    	if(Num < Other.Num) return 1;
        if(Num > Other.Num) return 0;
        
        return Name < Other.Name;
}

priority_queue<Node> CustomPQ;