[C++, STL] 알고리즘 문제풀이를 위한 우선순위 큐(priority queue)

by

서론

우선순위

신용카드 신청을 위해 상담사와 통화를 했다. 급하게 받아야 해서 금요일까지 수령할 수 있겠냐고 여쭸더니 긴급으로 발송해주겠다고 한다. 원래는 신청받은 순서대로 발송을 하겠지만 내 카드는 우선순위를 높여서 먼저 발송해 줄것이다.

큐와 우선순위 큐

[C++, STL] 알고리즘 문제풀이를 위한 큐(queue)

우선순위 큐는 우선순위가 포함된 자료가 들어간다. 그러면 큐 내부에서 pop을 했을 때 가장 우선순위가 높은 자료가 먼저 나올 수 있도록 재배열한다. 모든 자료의 우선순위가 같다면 큐와 동일하게 작동한다.

어떤 자료가 우선순위를 갖는지에 따른 규칙은 사용자가 지정할 수 있다. 그리고 자료와 우선순위를 함께 넣을 수도 있고 자료 그 자체가 우선순위를 가질 수도 있다.

우선순위 큐의 다양한 구현방법

우선순위 큐는 배열, 연결리스트, 힙으로 구현 가능하다. 배열과 연결리스트는 새로운 자료가 추가되면 기존의 모든 자료와 우선순위를 비교한다. 반면에 힙은 트리 구조로 이루어져 있어서 자신의 부모 노드들만 우선순위를 비교하면 되기 때문에 배열과 연결리스트 대비 시간복잡도에서 유리하다.

힙으로 구현되면 모든 노드가 우선순위로 정렬되어 있지는 않다. 다만 top은 항상 가장 우선순위가 높은 값으로 정렬되어 있고, 우선순위 큐는 랜덤 엑세스를 지원하지 않기 때문에 문제가 되지 않는다.

힙은 바이너리 힙(Binary Heap)과 피보나치 힙(Fibonacci Heap)으로 구현할 수 있다. 피보나치 힙은 이론적으로 시간복잡도가 바이너리 힙보다 유리하지만 효율적으로 구현하기가 현실적으로 어렵다. 그래서 STL에서는 바이너리 힙으로 우선순위 큐가 구현되어 있다.

시간복잡도배열 / 연결리스트바이너리 힙피보나치 힙
top(참조)O(1)O(1)O(1)
push(enqueue)O(N)O(logN)O(1)
pop(dequeue)O(1)O(logN)O(logN)

우선순위 큐 활용 예

  • 프림 알고리즘(Prim’s Algorithm)
  • 다익스트라 알고리즘(Dijkstra’s Algorithm)
  • 허프만 코드(Huffman Code)

헤더파일

우선순위 큐는 큐 클래스 내부에 있다. 네임스페이스는 std를 사용한다.

#include <queue>
using namespace std;

우선순위 큐 선언

priority_queue<자료형, 컨테이너, 우선순위>이름

자료형 : int, string, struct 등

컨테이너 : vector, deque

  • 생략했을 시 기본 컨테이너는 vector
  • 리스트와 같이 랜덤 엑세스가 불가능한 컨테이너는 이용할 수 없다.

우선순위 : greater<자료형>, less<자료형>, 비교연산자

  • 생략했을 시 기본 우선순위는 less<자료형>
  • greater<자료형> : 오름차순 정렬
  • less<자료형> : 내림차순 정렬

기본형

컨테이너는 벡터, 우선순위는 내림차순으로 기본 지정되어 있다. 그래서 자료형만 입력한다.

priority_queue<int>pq; // 자료형은 정수, 내림차순 정렬(가장 큰 정수가 top에 위치)

컨테이너 변경

기본 컨테이너인 벡터를 덱으로 변경한다.

priority_queue<int, deque<int>>pq; // 자료형은 정수, 컨테이너는 덱

우선순위 변경

오름차순으로 우선순위를 변경한다.

priority_queue<int, vector<int>, greater<int>>pq; // 자료형은 정수, 컨테이너는 벡터, 오름차순 정렬

멤버 함수

push(원소)

우선순위 큐에 원소를 추가한다.

priority_queue<int>pq;
pq.push(1);
pop()

우선순위 큐에서 우선순위가 가장 높은 원소를 제거한다.

priority_queue<int>pq; // 우선순위를 내림차순으로 선언
pq.push(1); // top : 1
pq.push(2); // top : 2
pq.pop(); // top : 1(top인 2가 제거되었음)
top()

우선순위 큐에서 가장 우선순위가 높은 원소를 리턴

priority_queue<int>pq; // 우선순위를 내림차순으로 선언
pq.push(1);
cout<<pq.top(); // 출력 : 1
pq.push(3);
cout<<pq.top(); // 출력 : 3
pq.push(2);
cout<<pq.top(); // 출력 : 3
size()

우선순위 큐의 원소 개수를 리턴

priority_queue<int>pq; // 우선순위를 내림차순으로 선언
pq.push(1);
cout<<pq.size(); // 출력 : 1
pq.push(3);
cout<<pq.size(); // 출력 : 2
pq.push(2);
cout<<pq.size(); // 출력 : 3
empty()

우선순위 큐가 비어있으면 1, 아니면 0을 출력

priority_queue<int>pq;
cout<<pq.empty(); // 출력 : 1
pq.push(1);
cout<<pq.empty(); // 출력 : 0

참고

https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%ED%9E%99
https://docs.microsoft.com/en-us/cpp/standard-library/priority-queue-class?view=vs-2019

Leave a Comment