[C++] [STL] Priority_queue (feat. 여러 기준으로 우선순위 큐 구현해보기)

우선순위 큐 (Priority_queue)

큐(Queue) 선입선출(First In First Out) 구조였다면

우선순위 큐(Priority Queue)는 들어온 순서가 아닌 우선순위에 따라 먼저 처리되는 구조이다.

내부적으로 Heap 자료 구조가 구현되어 있다.

▶ 우선순위 큐 (Priority Queue) ← STL 없이 직접 구현해보기 

▶ 힙(Heap) 자료구조란?

우선순위 큐 (Priority Queue)

힙(Heap) 자료구조란?

 

생성자

- 헤더파일: #include <queue>

- 생성자 형태

① 기본 생성자 형식: priority_queue < [Data Type] > [변수이름];

    priority_queue<int> pq;

② 내부 컨테이너 변경: priority_queue < [Data Type], [Container Type] > [변수이름];

    priority_queue<int, deque<int> > pq;

③ 정렬 기준 변경: priority_queue < [Data Type], [Container Type], [정렬기준] > [변수이름];

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

※ 만약 정렬 기준을 주지않으면 기본적으로 내림차순(less)으로 정렬된다.

    정렬 기준은 다양한 방법으로 변경할 수 있다.

 

멤버 함수

- push(val): val 원소 삽입

- pop(): 우선순위가 높은 원소 삭제 (값 반환 X)

- top(): 맨 위에 있는 원소 반환 (삭제 X)

- empty(): 비어있는지 확인 (true / false)

- size(): 원소 개수 반환

#include <iostream>
#include <queue>

using namespace std;

int main() {
       // priority_queue<int> pq; // 내림차순
       priority_queue<int, vector<int>, greater<int>> pq; // 오름차순
       
       pq.push(5);   // 5
       pq.push(2);   // 2 5
       pq.push(4);   // 2 4 5
       pq.push(5);   // 2 4 5 5
       pq.push(1);   // 1 2 4 5 5
       pq.push(3);   // 1 2 3 4 5 5
       cout << "size: " << pq.size() << endl;
       
       while (!pq.empty()) {
              cout << pq.top() << " ";
              pq.pop();
       }
       cout << endl;
}

 

우선순위 큐 (비교)기준 변경

코딩 테스트는 객체 저장이나 2가지 기준으로 비교하는 문제가 나오기도 한다.

단순 정수 비교 뿐만 아니라 문자열 비교까지 연습해두면 좋다.

ex) {이름} (1차 기준, 오름차순) + {ID} (2차 기준, 오름차순)

       [(1, 까망 하르방), (2, 까망 포레스트)] → [(2, 까망 포레스트), (1, 까망 하르방)]

 

▶ BOJ 21608 상어 초등학교

[BOJ] 백준 21608 상어 초등학교

 

구조체 + 연산자 오버로딩 활용

#include <iostream>
#include <queue>

using namespace std;

struct Blog {
    int id;
    char name;
    Blog(int _id, char _name) : id(_id), name(_name) {}
    bool operator<(const Blog tg) const {
        if (name > tg.name)
            return true;
        else if (name == tg.name)
            return id >= tg.id;
        return false;
    }
    
    void printState()
    {
        cout << "(" << id << ", " << name << ")"<< endl;
    }
};

int main() {
    priority_queue<Blog> pq;

    pq.push(Blog(1, 'H')); // (1, H)
    pq.push(Blog(2, 'F')); // (2, F) (1, H)
    pq.push(Blog(0, 'F')); // (0, F) (2, F) (1, H)

    while (!pq.empty()) {
        Blog blog = pq.top();
        pq.pop();
        blog.printState();
    }
}

 

comp 구조체 활용

경우에 따라서는 한 개의 "비교 기준"이 아닌 여러 기준이 있을 수 있다.

ex) 매년 정책이 달라지거나 확장.

→ priority_queue < [Data Type], [Container Type], [정렬기준] > [변수이름];

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

#include <iostream>
#include <queue>
#include <String>

using namespace std;

struct Blog {
    int id;
    string name;
    Blog(int _id, string _name) : id(_id), name(_name) {}
    void printState()
    {
        cout << "(" << id << ", " << name << ")" << endl;
    }
};

struct comp {
    bool operator()(Blog A, Blog B)
    {
        if (A.name > B.name)
            return true;
        else if (A.name == B.name)
            return A.id >= B.id;
        return false;
    }
};

int main() {
    priority_queue<Blog, vector<Blog>, comp> pq;
    pq.push(Blog(1, "Harbang")); // (1, H)
    pq.push(Blog(2, "Forest")); // (2, F) (1, H)
    pq.push(Blog(0, "Forest")); // (0, F) (2, F) (1, H)
    while (!pq.empty()) {
        Blog blog = pq.top();
        pq.pop();
        blog.printState();
    }
}

 

Reference

- [BOJ] 1966 프린터큐