우선순위 큐(Priority queue)

공부(Archive)/Data structure 2019. 6. 12. 12:40

우선순위 큐는 큐와 같이 FIFO와 비슷한 특징을 갖는다.

다른 점이 있다면 큐에 있는 원소를 처리할 때 가장 먼저 들어온 원소를 먼저 처리하는 것이 아닌

우선순위가 가장 높은 원소가 빠져나간다.

따라서 우선순위 큐에 저장되는 원소들은 모두 우선순위를 갖는다.

얼마 전까지 우선순위 큐는 항상 힙으로 구현되는 줄 알았는데 검색을 해보며 찾아보니 아니라는 것을 알게 되었다.

"우선순위 큐가 힙이라는 것은 널리 알려진 오류이다. 우선순위 큐는 "리스트"나 "맵"과 같이 추상적인 개념이다; 마치 리스트는 연결 리스트나 배열로 구현될 수 있는 것과 같이, 우선순위 큐는 힙이나 다양한 다른 방법을 이용해 구현될 수 있다."

사실 알고리즘을 공부하면서 이런저런 자료구조에 대해서도 공부를 했지만 직접 구현해본 적은 별로 없는 것 같다. 그래서 구현보다는 자주 사용하는 언어인 C++에 있는 STL을 소개하고자 한다.

~~(구현은 다음에 해보자라고 맨날 미루게 된다.)~~

먼저 우선순위 큐는 queue 헤더의 std namespace에 저장되어 있다.

#include<queue>
using namespace std;

queue 헤더 파일을 열어보면, 컨테이너로 구현이 되어있고

push, pop 연산이 다음과 같이 구현되어 있는 것으로 미루어 보았을 때 힙을 이용해서 구현을 해놓은 듯하다.

우선순위 큐를 사용할 때는 다음과 같은 멤버 함수들을 주로 사용한다.

함수	설명	시간 복잡도
push()	우선순위 큐에 원소를 저장한다.	O(logN)
pop()	우선순위 큐에서 우선순위가 가장 높은(낮은) 원소를 빼낸다.	O(logN)
top()	우선순위 큐에서 우선순위가 가장 높은(낮은) 원소를 반환한다.	O(1)
size()	우선순위 큐의 크기를 반환한다.	O(1)

사용하는 공간은 O(N)으로 생각하면 될 것 같다.

우선순위 큐는 다음과 같이 사용할 수 있다.

priority_queue<int> q;

q.push(1);
q.push(2);
q.push(3);

while(q.size()){
	printf("%d ", q.top());
    q.pop();
}

위 코드의 결과는 3 2 1 이 나온다.

int type을 저장할 우선순위 큐를 선언하고,

큐에 1, 2, 3을 순서대로 삽입하고,

큐가 비어있지 않은 동안 우선순위가 가장 높은 원소를 출력하고 제거한다.

우선순위 큐의 default 설정은 우선순위가 높은 원소가 먼저 처리되게 되어있다. (최대 힙)

priority_queue<int, vector<int>, less<int>> q;

우선순위가 낮은 원소를 먼저 처리하고 싶은 경우에 사용할 수 있는 몇 가지 방법이 있다.

첫 번째 방법으로는 greater를 이용하여 선언하는 방법이다.

priority_queue<int, vector<int>, greater<int>> q;

두 번째 방법으로는 우선순위 큐에 넣어서 비교할 대상에 -를 붙여서 넣는 방식이다.

priority_queue<int> q;

q.push(-1);
q.push(-2);
q.push(-3);

while(q.size()){
	printf("%d ", -q.top());
    q.pop();
}

이 방법은 넣을 땐 -를 붙여야 한다고 인식하고 코딩을 하지만, top()과 같은 함수를 이용할 때 -를 붙이는 것을 종종 까먹곤 하여 낭패를 보기도 한다. 주의해서 사용하자.

세 번째 방법으로는 연산자 오버로딩이다.

Primitive type을 이용할 때에는 별로 좋은 방법은 아니라고 생각되지만 원소로 넣을 데이터가 구조체 등의 자료라면 한 번쯤 고려해볼 만하다.

안홍자가 혼자 공부하면서 써보는 블로그 안홍자가 혼자 공부하면서 써보는 블로그