[자료구조/C++] 우선순위 큐

[ 1 ]  기본내용

우선순위 큐(Priority Queue)란 First-In First-Out(FIFO) 구조를 따르는 일반적인 큐와 달리 힙(heap)을 활용하여 원소들의 우선순위를 설정하고, 우선순위에 따라 가장 작은(또는 가장 큰) 원소에 빠르게 접근할 수 있는 자료구조이다. 단, 최대 or 최소 둘 중 하나에 대해서만 우선순위를 적용할 수 있으며 최댓값을 우선순위로 둘 경우 최대 힙(Max heap), 최솟값을 우선순위로 둘 경우 최소 힙(Min heap)이라 한다.

 

[ 2 ] C++에서의 우선순위 큐

 [ 2 -1 ] 헤더파일

C++에서는 container adaptor로서 priority_queue를 제공하고 있으며, vector를 기본 컨테이너로 사용한다.

priority_queue를 사용하기 위해서는 우선 queue 헤더파일을 include 해야 한다.

 

#include <queue>

 

 [ 2 -2 ] 멤버 함수

priority_queue의 멤버 함수는 queue와 비슷하며 vector 컨테이너를 알고 있다면 쉽게 이해할 수 있을 것이다.

멤버 함수	기능
empty	priority_queue가 비어있다면 true, 비어있지 않다면 false를 return
size	priority_queue의 크기를 return
push	priority_queue에 새로운 원소를 삽입
pop	priority_queue에서 우선순위가 가장 높은 값을 제거
top	priority_queue에서 우선순위가 가장 높은 값을 return (제거 X)
emplace	push와 기능은 같으나, 새로운 원소가 추가될 위치에 해당 원소를 바로 생성하는 함수 (성능 향상)
swap	두 개의 priority_queue를 swap. 즉, 내부 원소를 바꿈

※ push의 경우 함수가 추가할 원소를 먼저 임시로 생성한 후, 버퍼 내부 위치로 복사 또는 이동을 수행한다. 즉, 불필요한 복사가 많이 일어난다는 단점이 있다. emplace는 새로운 원소가 추가될 위치에 해당 원소를 바로 생성하며 push의 단점을 해결한다.

즉, push의 매개변수는 '생성된 객체'여야 하고(객체를 만들고 전달), emplace에는 생성자에 필요한 매개변수를 직접 전달해야 한다(전달된 매개변수로 적절한 객체 바로 생성 후 삽입).

 

 [ 2 - 3 ] 기본 예제

다음은 priority_queue의 예제이다. C++의 priority_queue는 기본적으로 최대 힙(Max heap)으로 만들어지기 때문에 원소가 들어오는 순서에 상관없이 큰 값부터 출력되는 것을 확인할 수 있다.

#include <queue>
using namespace std;

int main(void) {
    priority_queue<int> pq;
    
    pq.push(1);
    pq.push(5);
    pq.push(3);
    pq.push(4);
    
    // 우선순위 큐가 비어있지 않다면 반복
    while(!pq.empty()) {
    	cout << pq.top();
        pq.pop();
    }
    
    // 원소가 들어온 순서와 상관없이
    // 5431 이 출력된다.
    return 0;
}

 

[ 2 - 4 ] 기본 구조

최소 힙(Min heap)을 구현하기 위해서는 priority_queue의 기본구조를 이해해야 한다.

- priority_queue<자료형, 내부 컨테이너, 비교함수 객체> pq;

 

(1) 자료형: int ,double 등 기본자료형 및 구조체, 클래스

(2) 내부 컨테이너: container adaptor이기 때문에 기본적인 구현체가 존재한다. 일반적으로 vector로 구현하며, 다른 컨테이너로도 구현 가능

(3) 비교함수 객체: 우선순위를 결정할 기준을 설정하는 비교함수 객체. 함수 객체이므로 새로운 '구조체'를 작성해야 한다.

 

위 예제처럼 내부 컨테이너와 비교함수 객체를 설정하지 않으면

priority_queue<자료형, vector<자료형>, less<자료형>> pq; 가 default 설정이기 때문에 최대 힙(Max heap)으로 구현된다.

 

그러므로 최소 힙(Min heap)을 구현하기 위해서는 비교함수 객체를 greater<자료형>으로 변경한다.

#include <queue>
using namespace std;

// 최소 힙
priority_queue<int, vector<int>, greater<int>> pq;

 

[ 3 ] 우선순위 큐 활용 문제 - 백준

비교함수 객체를 직접 만들어 절댓값을 기준으로 우선순위 큐를 구현할 수도 있는데, 이는 백준 [11286 - 절댓값 힙] 문제 풀이로 확인해 보자.

 

문제 출처: https://www.acmicpc.net/problem/11286

11286번: 절댓값 힙

다음은 해당 문제의 소스코드이며 절댓값이 같을 때는 더 작은 수가 heap의 top이 될 수 있도록, 절댓값이 다를 때는 절댓값이 더 작은 수가 heap의 top이 될 수 있도록 비교함수 객체를 작성했다.

#include <iostream>
#include <cstdlib>
#include <queue>

using namespace std;

struct cmp{
	bool operator()(int a, int b) {
		if ( abs(a) == abs(b) )
		{
			return a > b;
		}
		else
		{
			return abs(a) > abs(b);
		}
	}
};

int main(void)
{
	priority_queue<int, vector<int>, cmp> pq;
	int n, x;
	scanf("%d", &n);
	
	for ( int i = 0 ; i < n ; i++ )
	{
		scanf("%d", &x);
		if ( x == 0 )
		{
			if ( !pq.empty() )
			{
				printf("%d\n", pq.top());
				pq.pop();
			}
			else
			{
				printf("%d\n", 0);
			}
		}
		else
		{
			pq.push(x);
		}
	}
	
	return 0;
}