[C++/STL] 우선순위 큐 (Priority Queue) 사용법

1. 우선순위 큐란 무엇인가?

'선입선출(FIFO, First In First Out)'으로 대변되는 큐 자료형의 기본적인 기능에, 우선순위가 높은 자료형을 가장 먼저

삽입 및 삭제할 수 있게 한 자료형이다. 이러한 우선순위 큐는 운영체제 스케줄링 등 다양한 곳에서 사용된다.

 

 

2. C++ 에서의 사용방법

큐가 그렇듯이, C++에서는 STL을 통해서 사용자가 간편하게 정의하고 사용할 수 있다.

기본적인 사용 방법은 다음과 같다.

#include <queue>

priority_queue<int, vector<int>, less<int>> pq;
pq.push(5);
pq.push(8);

pq.pop();
pq.pop();

• priority_queue<T, Container, Compare>

이는 우선순위 큐의 선언이다.

T는 원하는 자료형 및 클래스, Container는 vector와 같은 컨테이너, Compare는 비교함수 이다. 

여기에서 Compare는 우선순위 큐에 삽입할 때 우선순위에 따른 처리를 할 수 있게 해주는 함수를 말한다.

Compare 함수는 다음과 선택하여 같이 사용할 수 있다.

#include <functional>

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

// Max-Heap의 선언
priority_queue<int, vector<int>, less<int>> max_pq;

 

3. 나만의 우선순위 비교함수 만들어서 사용하기

위의 우선순위 비교함수는 <functional>을 include하여 기본적으로 제공되는 함수를 사용한 것이다.

하지만 나만의 구조체를 적용하여 사용한다면 다음과 같이 선언하여 사용할 수 있다.

struct item {
	int idx;
	int priority;
    
    // struct item의 생성자 선언
    item(int idx, int priority) : idx(idx), priority(priority) {}
};

struct cmp {
	bool operator()(item item1, item item2) {
    	// Min Heap의 예이다. Max-Heap이라면 item1.priority < item2.priority
    	return item1.priority > item2.priority;
    }
}

priority_queue<item, vector<item>, cmp> pq;

이 예제에서는 int 자료형 2개를 가지는 구조체를 선언하였고, 구조체 멤버를 비교하는 함수를 선언하여 사용하였다.