우선순위 큐

 ∙ 우선순위 큐 (priority queue)

- 각각의 데이터에 우선순위가 정의되어 있어서, 입력 순서에 상관없이 우선순위가 가장 높은 데이터가 먼저 출력되는 형태의 자료 구조

- 우선순위의 예 : 응급 자동차, 네트워크 트래픽 우선순위, 운영체제에서 프로그램 우선순위

- 일반 선출(FIFO) 큐 : 큐에 머무른 시간을 우선순위로 설정하면 일반 큐와 같이 동작

- C++에서 우선순위 큐 사용하기

> STL에서 제공하는 std::priority_queue 컨테이너 사용

 

∙ std::priority_queue

- 우선순위 큐의 기능을 제공하는 컨테이너 어댑터

- 삽입 순서에 상관없이 우선순위가 가장 높은 원소가 먼저 출력됨

- 사용자 정의 타입을 저장할 경우, 비교 연산을 지원해야 함

- <queue>에 정의되어 있음

- 주요 멤버 함수

> priority_queue::push(e) : 우선순위 큐에 원소 e를 추가 O(log n)

> priority_queue::pop() : 우선순위 큐의 최상위 원소를 제고 O(log n)

> priority_queue::top() : 우선순위 큐의 최상위 원소를 참조 O(1)

 

∙priority_queue 실습

#include <iostream>
#include <queue>
#include <string>
#include <vector>

using namespace std;

// pq1, pq2 타입 형태가 다르기 때문에 template 사용
template <typename T>
void print_queue(T q)
{
    while (!q.empty()) {
        cout << q.top() << ", ";
        q.pop();
    }
    cout << endl;
}

// score가 높은 우선순위 비교 클래스
class Student
{
public:
    string name;
    int score;

    bool operator < (const Student& st) const
    {
        return score < st.score;
    }
};

int main()
{
    vector<int> vec {4, 2, 3, 5, 1};

    priority_queue<int> pq1;
    for (auto n : vec)
        pq1.push(n);
    print_queue(pq1);

    priority_queue<int, vector<int>, greater<int>> pq2(vec.begin(), vec.end());
    print_queue(pq2);

    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();
    }
}