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

Priority_queue란?

• C++에서 자주 사용되는 vector와 같은 container adapter의 한 종류이다
• 만약 int와 같은 기본 자료형으로 우선순위 큐를 사용한다면, 큐에 있는 모든 원소 중에서 가장 큰 값이 Top을 유지하도록(=우선순위가 가장 크도록) 설계되어 있다
• 우선순위 큐는 내부적으로 Heap이라는 자료구조를 사용한다
• #include <queue>에 포함되어 있다

 

기본적인 메소드

• push( ) : 원소 추가
• pop( ) : top의 원소를 제거
• top( ) : top에 있는 원소(=우선순위가 높은 원소)를 반환
• empty( ) : 우선순위 큐가 비어있는 경우 true, 아닌 경우 false를 반환
• size( ) : 우선순위 큐에 포함되어 있는 원소의 수 반환

 

사용 예시

우선순위 큐는 기본적으로 내림차순으로 정렬한다

오름차순으로 정렬하려면 priority_queue<int, vector<int>, greater<int> > q; 로 하면 된다!

#include <iostream>
#include <string>
#include <queue>
using namespace std;

int main() {
	// priority_queue<int> q;	// 내림차순 
	// priority_queue<int, vector<int>, less<int> > q;	// 내림차순
	priority_queue<int, vector<int>, greater<int> > q;	// 오름차순

	if (q.empty()) cout << "우선순위 큐가 비었습니다.\n";

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

	cout << "맨 위 : " << q.top() << "\n";


	cout << "나가는 순서 : ";
	while (!q.empty()) {
		cout << q.top() << " ";
		q.pop();
	}
	cout << "\n";

	return 0;

---

일단은 간단하게 이정도면 공부하고 마저 문제 풀러 빠잉