[Algorithm] priority queue

[Algorithm] priority queue

 

기본 형태

priority_queue<T, Container, Compare>

• T(자료형)은 int, double, 등등이 들어간다.
• Container(구현체)는 기본적으로 vector<자료형>으로 정의 된다. 즉, priority_queue가 실제로는 vector 위에서 돌아가고 있다는 의미이다. vector외에 heap을 구현하기에 충분한 자료구조를 넣으면 된다.
• Compare(비교연산자)는 기본적으로 less<자료형>으로 정의된다. 이것은 STL에서 기본적으로 제공하는 비교 연산자 클래스인데, 사용시 큰 값부터 나오게 된다. greater<자료형>을 넣으면 작은 값부터 나온다. 여기에 새로 만들어준 클래스를 사용할 수 있다.

함수

push(element) : 우선순위 큐에 원소 추가

pop() : 우선순위 큐에서 top의 원소 삭제

top() : 우선순위 큐에서 top에 있는 원소를 반환

empty() : 비어있으면 true아니면 false를 반환

size() : 우선순위 큐에 포함되어 있는 원소들의 수를 반환

 

 

구현

 

#include <iostream>
#include <queue>
#include <functional>

using namespace std;

int main(void){
	priority_queue< int, vector<int>, less<int> > pq;
    
    pq.push(3);
    pq.push(5);
    pq.push(4);
    pq.push(9);
    
    pq.pop();
    
    cout << "pq top: " << pq.top() << "\n";
    
    if(!pq.empty()) cout << "pq size: " << pq.size() << "\n";
    
    return 0;

 

 

참고

https://koosaga.com/9

https://twpower.github.io/93-how-to-use-priority_queue-in-cpp