[c++/queue/heap] STL::priority_queue (우선순위 큐)

우선순위 큐란?

일반적인 큐와 달리 선입선출 구조가 아닌 큐에 있는 모든 원소 중에서 가장 큰 값이 top을 유지하도록, 우선순위가 가장 크도록 설계되어있다. 또한 내부적으로 heap이라는 자료구조를 사용하고있다.

#include <queue> 선언해야한다.

​

 

기본 메소드

• push() : 　 우선순위 큐에 원소를 추가한다
• pop() : 우선순위 큐에서 top의 원소를 제거한다
• top() : 우선순위 큐에서 top에 있는 원소 즉 우선순위가 높은 원소를 반환한다.
• empty() : 우선순위 큐가 비어있으면 true를 반환하고 그렇지 않으면 false를 반환한다
• size() : 우선순위 큐에 포함되어 있는 원소의 수를 반환한다

​

​

기본 자료형 사용법

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> pq;  // - >  priority_queue<int, vector<int>, less<int>> pq;
 
    // 우선순위 큐에 원소를 삽입 (push) 한다 
    pq.push(4);
    pq.push(7);
    pq.push(3);
    pq.push(1);
    pq.push(10);
 
    cout << "우선순위 큐 사이즈 : " << pq.size() << "\n";   // 5
    // 우선순위 큐가 비어 있지 않다면 while 문을 계속 실행
    while (!pq.empty()) {
        cout << pq.top() << '\n';   // 10 7 4 3 1
        pq.pop();
    }
    return 0;
}

가장 큰 값부터 출력되는 것을 볼 수 있다. 작은 값부터 출력하고 싶을 때는

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

다음과 같이 우선순위 큐를 선언해주어야 한다.

​

​

​

구조체 활용 및 구조체 내부 연산자 오버로딩

​

학번을 기준으로 우선순위가 높게 설정을 해봤다. 구조체 내부의 연산자 오버로딩 부분을 조작하면 수학 점수와 영어 점수를 기준으로 우선순위 큐 내부의 우선순위를 설정할 수 있다.

struct Student{
    string name;
    int score;
    
    bool operator < (const Student& st) const{    //정의 꼭 따로 해줘야함. 없으면 오류남
        return score < st.score;
    }
};

int main(){
    priority_queue<Student> students;
    students.push({"Amelia",80});
    students.push({"Sophia",40});
    students.push({"Olivia",95});
    students.push({"George",70});
    
    //출력
    while(!students.empty()){
        auto& s=students.top();
        cout<<s.name<<"("<<s.score<<")"<<endl;
        students.pop();
    }
    
    //Olivia (95)
    //Amelia (80)
    //Geroge (70)
    //Sophia (40)
}

struct 안에 operator 꼭 지정해줘야한다. 아니면 작동이 아예 안됨 (오류남)