[C++] STL 우선순위 큐(priority queue)

오늘 공부할 부분은 STL(Standard Template Library)의 우선순위 큐(priority queue)이다. 우선순위 큐는 말 그대로 큐이지만, pop을 할 때 가장 큰 값이 빠져나온다. 또는 임의의 우선순위를 주는 함수를 만들어서 해당 우선순위에 해당하는 값이 먼저 pop 하여 사용할 수 있다. 차례대로 선언방법과 기본적인 사용법을 알아보겠다.

• 헤더 파일은 queue를 사용한다.
• 선언은 priority_queue<[type]> pq; 와 같이 한다.
• pq.push([input]); 와 같이 값을 넣는다.
• pq.pop(); 을 수행하면 우선순위가 가장 높은 값이 빠져나온다.(위의 선언에서는 가장 큰 값이 빠져나온다.)
• pq.empty(); 를 통해서 우선순위 큐가 비어있는지를 확인할 수 있다. 비어있다면 1이 반환된다.
• pq.size(); 를 통해서 원소의 개수를 반환한다.
• pq.top(); 를 통해서 가장 우선순위가 높은 원소를 반환한다. 삭제되지 않는다.

거의 큐를 사용한 그대로 사용을 하면 된다. 하지만 큰 값에 우선순위를 두는 것이 아닌 새로운 우선순위를 정해서 정의하고자 한다면 다음과 같다.

• priority_queue<자료형, 구현체(container), 비교 연산자(compare 함수)> 와 같이 정의할 수 있다.
• 자료형에는 int, double, class 등이 들어갈 수 있다.
• 구현체는 기본적으로 vector<자료형>이다. 값의 저장방식을 결정할 컨테이너이다.
• 비교 연산자는 말 그대로 비교에 사용할 연산을 적는다. 
• 기본값은 less 이므로 내림차순이고, greater를 사용할 경우 오름차순으로 우선순위큐가 정렬된다. 
• ex) priority_queue<int, vector<int>, greater<int>> pq;
• 만약 자료형에 pair가 들어간다면 pair<a, b>일 때, a의 값이 같다면 b의 값에 따라 우선순위가 결정된다.
• push 또는 pop을 할 때 시간복잡도는 logN 이다.