Priority Queue

• Queue의 한 종류
• 우선순위에 따라 정렬된 Queue
• 원소 삽입(push)시 우선순위에 맞춰 Queue가 정렬됨
• Heap으로 구현되어있음
• Push 중 생기는 정렬 과정의 시간 복잡도는 O(logN)
  
  

1. 생성

• 헤더 파일
  #include <queue> (Queue와 동일)

• 생성
  priority_queue<자료형> 변수명
priority_queue<자료형, Container, 비교함수> 변수명

자료형만 명시할 경우 Default는 내림차순

ex) priority_queue<int, vector, greater> pq; // 오름차순에 따라 정렬되는 우선순위 큐 생성

2. 멤버 함수

종류	상세설명
empty()	비어있는지 확인
size()	사이즈 반환
top()	맨 앞의 원소 리턴
push(n)	큐에 원소를 추가(비교함수에 따라 내부적으로 정렬됨)
pop()	맨 앞의 원소를 삭제

3. 예시

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

void main() {
	priority_queue<int> pq1;

	pq1.push(1);
	pq1.push(8);
	pq1.push(3);
	pq1.push(5);

	for (int i = 0; pq1.size(); i++) {
		cout << pq1.top() << endl; // 8 5 3 1
		pq1.pop();
	}
	cout << pq1.empty() << endl; // 1(true)

	priority_queue<int, vector<int>, greater<int>> pq2;
	pq2.push(1);
	pq2.push(8);
	pq2.push(3);
	pq2.push(5);

	for (int i = 0; pq2.size(); i++) {
		cout << pq2.top() << endl; // 1 3 5 8
		pq2.pop();
	}
	cout << pq2.empty() << endl; // 1(true)

}

참고

• http://www.cplusplus.com/reference/queue/priority_queue/
• https://travelbeeee.tistory.com/126