[STL] Priority Queue

 Priority Queue(우선순위 큐)는 Least-First-Out 혹은Large-First-Out의 자료구조로, Heap(힙)이라는 자료구조를 가지고 구현된다.

Queue와 달리, 데이터를 넣은 순서에 상관없이 우선순위가 높은 것부터 꺼낼 수 있다.

Priorty Queue는 C++의 표준 템플릿 라이브러리에 담겨있다. #include <queue>

 

기본 형태 

priority_queue<T, Container, Compare>

자료형 및 클래스 T, vector<T>와 같은 컨테이너 Container, 비교 함수 클래스 Compare을 매개변수로 가진다. 이때, vector의 type은 T와 같다.

 

• priority_queue<int> pq를 선언하면 Default로 Container는 vector<int>, Compare은 functional 라이브러리의 less<int>가 된다. 따라서 우선순위 큐의 기본 정렬 방법은 내림차순이다.

 

 

기본 함수

top()	우선순위 큐의 top에 있는 원소를 반환
push(element)	우선순위 큐에 원소 추가
pop()	우선순위 큐의 top을 반환하고 삭제
empty()	우선순위 큐가 비어있으면 true, 아니면 false를 반환
size()	우선순위 큐의 사이즈를 반환

 

---

Compare 클래스

1. Default로 우선순위 큐를 내림차순으로 정렬한다.
2. less<type>을 사용하여 우선순위 큐를 내림차순으로 정렬한다.(#include functional)
3. greater<type>을 사용하여 우선순위 큐를 오름차순으로 정렬한다.(#include functional)
4. 연산자 오버로딩을 통해 구조체를 선언하여 우선순위를 정한다. operater()의 첫 번째 매개변수를 기준으로 결과가 True이면 두 번째 매개변수의 밑에 정렬되고, False이면 위에 정렬된다.

 

▶ Default 예제

//
//  main.cpp
//  pqtest
//
//  Created by Hwayeon on 2021/02/02.
//
#include<iostream>
#include<queue>
using namespace std;

int main(int argc, const char * argv[]) {
    priority_queue<int> pq;
    pq.push(2);
    pq.push(5);
    pq.push(1);
    pq.push(3);
    pq.push(9);

    while(!pq.empty()){
        cout << pq.top() << endl;
        pq.pop();
    }
    
    return 0;
}

 

 

 

▶ less<type> 사용 예제

//
//  main.cpp
//  pqtest
//
//  Created by Hwayeon on 2021/02/02.
//
#include<iostream>
#include<queue>
using namespace std;

int main(int argc, const char * argv[]) {
    priority_queue<int, vector<int>, less<int>> pq;
    pq.push(2);
    pq.push(5);
    pq.push(1);
    pq.push(3);
    pq.push(9);

    while(!pq.empty()){
        cout << pq.top() << endl;
        pq.pop();
    }
    
    return 0;
}

 

 

 

▶ greater<type> 사용 예제

//
//  main.cpp
//  pqtest
//
//  Created by Hwayeon on 2021/02/02.
//
#include<iostream>
#include<queue>
using namespace std;

int main(int argc, const char * argv[]) {
    priority_queue<int, vector<int>, greater<int>> pq;
    pq.push(2);
    pq.push(5);
    pq.push(1);
    pq.push(3);
    pq.push(9);

    while(!pq.empty()){
        cout << pq.top() << endl;
        pq.pop();
    }
    
    return 0;
}

 

 

 

▶ 구조체 선언을 통한 비교 연산자 정의 예제

//
//  main.cpp
//
//  Created by Hwayeon on 2021/02/02.
//
#include<iostream>
#include<queue>
using namespace std;

struct Custom{
    int x;
    int y;
    int val;
};

struct cmp{
    bool operator()(Custom a, Custom b){
        return a.val > b.val;
    }
};

int main(int argc, const char * argv[]) {
    priority_queue<Custom, vector<Custom>, cmp> pq;
    pq.push(Custom{0, 0, 2});
    pq.push(Custom{0, 0, 5});
    pq.push(Custom{0, 0, 1});
    pq.push(Custom{0, 0, 3});
    pq.push(Custom{0, 0, 9});

    while(!pq.empty()){
        cout << pq.top().val << endl;
        pq.pop();
    }
    
    return 0;
}

 

 

 

 

 

 

---

참고

• 2021/02/03 - [C++] - [STL] functional

[STL] functional