[C++] Priority_Queue

특징

#include <queue>

• FIFO (선입선출)
• 우선순위 따른 정렬 (기본 내림차순)

 

생성

설명	코드
우선순위 큐 생성	priority_queue<int> pq

 

연산

설명	코드
우선 순위에 맞게 k 삽입	pq.push(k)
가장 큰 우선순위를 가진 원소 제거	pq.pop()
가장 큰 우선순위를 가진 원소 반환	pq.top()
우선순위 큐의 크기를 반환	pq.size()
우선순위 큐가 비어있으면 True, 아니면 False를 반환	pq.empty()

 

정렬 기준 바꾸기

• 일반적인 정렬의 비교연산과 반대이다

오름차순	내림차순
greater<int>	less<int>
return a > b	return a < b

• 우선순위 큐의 정렬을 커스텀할 때 구조체를 이용한다

//first를 기준으로 내림차순 정렬 
// first가 같으면 second를 기준으로 오름차순 정렬

struct cmp{
    bool operator()(pair<int,int>& a, pair<int,int>& b){
    	if(a.first == b.first)
        	return a.second > b.second;
        return a.first < b.first;
    }
};

priority_queue<pair<int,int>, vector<pair<int,int> >, cmp> pq;