[자료구조] 우선순위 큐 (Priority Queue) 개념, C++ STL

우선순위 큐란 큐의 한 종류로 말 그대로 우선순위대로 큐에 데이터를 집어넣는다. (여기서 말하는 우선순위란 값의 크기의 오름차순 혹은 내림차순 등 사용자가 정할 수 있다.)

 

일반적인 큐는 배열같은 선형적인 구조로 생각할 수 있다. 하지만, 우선순위 큐는 트리의 관점에서 접근해야 한다. 우선순위 큐는 배열 혹은 연결 리스트로도 구현이 가능하지만 이를 사용하지 않는 이유가 있다.

데이터를 삽입하거나 삭제하는 과정에서 배열이나 연결 리스트의 메모리를 밀고 당기는데에서 성능 저하를 일으키기 때문에 일반적으로 힙을 사용하여 구현하기 때문이다. (힙이 트리로 이루어졌기 때문)

 

그리고, 힙에서 데이터를 삽입하거나 삭제할 때는 시간 복잡도가 O(log N)이다.

(+ 힙 정렬이 N개의 데이터를 하나씩 다 빼오기(삭제) 때문에 시간 복잡도가 O(NlogN)인 것이다.)

 

[요약정리]

1. 일반적으로 힙의 구조를 사용한다.
2. 데이터를 삽입하거나 삭제할 때 O(log N)의 복잡도를 갖는다.

 

[C++ STL 문법]

<queue> 라이브러리에 선언되어있다. (큐와 동일하다.)

 

[선언 방법]

priority_queue<자료형, Container, 비교함수> q;

//일반적으로 내림차순으로 선언된다.
priority_queue<int> q; // 내림차순이 됨

//자료형이 int이고, 오름차순일 때
priority_queue<int, vector<int>, greater<int>> q;

//비교 함수를 직접 선언할 때
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct cmp {
	bool operator()(int a, int b) {
		return a > b;
	}
};

int main() {
	int n;
	cin >> n;
	priority_queue<int, vector<int>, cmp> q;
	
	for (int i = 0; i < n; i++) {
		q.push(i);
	}

	cout << q.top();

	return 0;
}
// 왜 함수인데 struct를 사용하는지 모르겠다.
// 그리고 내림차순으로 q에 넣고 싶었는데 그 반대로 작용한다.