[개념정리] priority_queue

priority_queue란

 

자료구조에서 우선순위큐는 먼저들어간데이터에 상관없이 우선순위가 높은 데이터가 먼저 반환되는 구조이다.

 

C++ STL에서 priority_queue를 이용하여 쉽게 구현해낼 수 있다.

 

vector container 기반으로 내부구조가 설정되어있다.

​

priority_queue사용

#include <queue>

 

선언

priority_queue<자료형>변수명; priority_queue<int>pq;

 

기본 사용

pq.push(element) // 우선순위큐에 원소 추가
 
pq.pop() //우선순위큐에서 top의 원소를 삭제

pq.top() //top에 있는 원소를 반환

pq.empty() //비어있으면 true 아니면 false 반환

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

기본적으로 내림차순으로 정렬되게 된다. 하지만 우선순위큐를 오름차순으로 바꿀 수 있다.

-> priority_queue<int, vector<int>, greater<int>>pq;

그렇다면 기본적인 내림차순 구조를 굳이 풀어쓴다면?

-> priority_queue<int, vector<int>, less<int>>pq;

 

pair를 이용한 사용

//priority_queue 에 greater 를 써서 오름차순으로 정렬해준다. 작은숫자가 먼저 나오게끔

priority_queue < pair<pair<int,int>,int>, vector<pair<pair<int,int>,int>>, greater<pair<pair<int,int>,int>> > pq;

// 내림차순은 기본

priority_queue < pair<pair<int, int>, int>> pq;

// push 

pq.push({{a,b},c});

 

 

struct를 이용한 사용

struct test{
    int x;
    int y;
    int z;
};

priority_queue<test, vector<test>> pq1; //기본 : 큰것 뽑을때

priority_queue<test, vector<test>, greater<test>> pq2; //작은것 뽑을때

 

 

compare를 통한 우선순위 정해주기

struct 사용 예시를 보면 분명 struct를 넣어줬는데 무엇을 기준으로 큰것, 작은것이 반환되는지 알 수 없다.

이를 지정해주기 위해 compare를 사용해준다.

struct test{
    int x;
    int y;
    int z;
};

struct compare{
    bool operator()(test a, test b){
        if(a.z == b.z){
            if(a.y == b.y){
                return a.x > b.x;
            }    
            return a.y > b.y;
        }
        return a.z > b.z;    
    }
}

priority_queue<test, vector<test>, compare> pq;

 

위의 코드에서는 우선순위를 z -> y -> x 순으로 잡은 것이고 오름차순 정렬을 수행한 예시이다.

 

좀더 간단한 예시로 보자.

struct compare{
    bool operator()(int a, int b){
        return a<b;
    }
};

priority_queue<int, vector<int>, compare> pq;

 

이번엔 pair 와 compare를 같이 사용해보자

 

struct compare{
    bool operator()(pair<int,int>a, pair<int,int>b){
        return a.second>b.second;
    }
};

priority_queue<pair<int,int>, vector<pair<int,int>>, compare> pq;