[Data Structure] Priority_queue(우선순위 큐) 사용법

• C++ STL중 하나인 Priority_queue에 대한 설명입니다.

Priority queue 이란?

• priority queue는 Compare(우선순위)에 맞게 설계된 container 입니다.
• priority queue는 heap과 유사합니다.
• #include < queue > 를 선언해야 priority queue를 사용할 수 있습니다.
• prioirty_queue < T, container< T >, compare > 형태
• 제너릭하게 구현되어 어떠한 type이라도 원소가 될 수 있으며, 기본 container는 vector 입니다.
• compare는 비교 클래스로 struct를 새롭게 구현하여 비교 클래스를 구현할 수 있습니다. ( 기본값으로 내림차순 )

---

기본 함수

empty( )

• 큐가 비어있는지 확인하는 함수
• if priority queue is empty, then return 1 else 0

size( )

• 큐의 크기를 반환하는 함수
• return size_type (unsigned int )

top( )

• 우선순위가 가장 큰 원소를 반환하는 함수
• return reference top element

push( element )

• 우선순위 큐에 원소를 추가하는 함수
• heap 구조이기 때문에 시간 복잡도 O(log n)

pop( )

• 우선순위가 가장 큰 원소를 삭제하는 함수
• heap 구조이기 때문에 시간 복잡도 O(log n)

swap( queue )

• 우선순위 큐를 바꾸는 함수

---

주의사항!!

• Compare에 들어가는 것은 비교 함수가 아닌 비교 클래스가 들어가야 합니다.
• less< int > => 비교 클래스, less< int >( ) => 비교 함수
• less< int >( )는 오름차순이다.
• 그러나, priority_queue에서 사용할 경우는 less< int >로 사용하고 내림차순이다!! (중요)

---

실습

	#include<iostream>
	#include<queue>
	using namespace std;
	// less<int> (오름차순) 구현
	struct cmp{
	bool operator()(int a,int b){
	return a<b;
	}
	};
	int main(){
	priority_queue<int,vector<int>, cmp> pq;
	priority_queue<int,vector<int>, cmp> pq2;
	if(pq.empty()){
	cout<<"pq가 비어있습니다"<<endl;
	}
	pq.push(5);
	pq.push(1);
	pq.push(4);
	pq.push(2);
	pq.push(3);
	cout<<"pq의 크기는 "<<pq.size()<<" 입니다"<<endl;
	while(!pq.empty()){
	cout<<pq.top()<<endl;
	pq.pop();
	}
	pq2.push(4);
	pq2.push(2);
	pq2.push(3);
	pq.swap(pq2);
	cout<<"pq와 pq2를 바꿉니다"<<endl;
	while(!pq.empty()){
	cout<<pq.top()<<endl;
	pq.pop();
	}
	}

view raw priority queue.cpp hosted with ❤ by GitHub

결과

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.