[C++ STL] Priority_queue 사용법

본 글은 여러 PS 문제를 접하다 보면 우선순위 큐를 적극적으로 사용해야 되는 경우가 있는데 매번 구글링을 하게 되는 것 같아  우선순위 큐에 대한 기본적인 사용법뿐만 아니라 기본적인 자료형 외에 구조체나 클래스의 객체 타입을 우선순위 큐에 저장하려고 할 때 비교 함수의 재정의 및 연산자 오버 로딩을 통한 우선순위 설정(?) 하는 방법을 알아보려고 합니다.

 

 

1. Priority_queue 란? 

기본적으로 C++에서 자주 쓰이는 vector와 같은 container adaptor의 한 종류이며 C++에서 int와 같은 기본자료형으로 우선순위 큐를 사용한다면 큐에 있는 모든 원소 중에서 가장 큰 값이 Top을 유지하도록, 우선순위가 가장 크도록 설계되어 있다 또한 우선순위 큐는  내부적으로 Heap이라는 자료구조를 사용하고 있다. 간단하게 이 정도로 소개하고 바로 사용법을 살펴보자.

 

 

 

2. 기본적인 메소드

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

 

3.  기본 자료형 사용법 (코드) 

 

기본적인 사용 방법은 다음과 같습니다

 

#include <iostream>
#include <queue>
#include <functional>    // greater, less
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";
    // 우선순위 큐가 비어 있지 않다면 while 문을 계속 실행
    while (!pq.empty()) {
        cout << pq.top() << '\n';
        pq.pop();
    }
    return 0;
}

 

 

결과에서 볼 수 있듯이 C++에서 기본적으로 가장 큰 값이 TOP을 유지하도록 설정되어 있기 때문에  가장 큰 값부터 출력되는 것을 볼 수 있다. 그렇다면 가장 작은 값부터 출력을 하기 위해서는 어떻게 해야 할까? 

 

조금은 복잡하긴 하지만 다음과 같이 우선순위 큐를 선언해 주어야 한다

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

 

또한 다른 방법으로서는 원소를 넣을 때 음수로 변환해서 넣게 되면 가장 큰 값이 TOP을 유지하는 특성상  절댓값이 가장 작은 값이 TOP을 유지하게 될 것이다 

 

 

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

우선은 구조체를 활용하여 학생들의 학번, 수학 점수와 영어점수를 표현하는 구조체를 선언하고 구조체 내부에서 연산자 오버 로딩을 통해서 우선순위 설정(?)을 해보았습니다

 

밑에 소스 코드는 학번을 기준으로 우선순위가 높게 (?) 설정을 해보았습니다 구조체 내부의 연산자 오버로딩 부분을 조작(?) 하면 수학 점수와 영어 점수를 기준으로 우선순위 큐 내부의 우선순위를 설정할 수 있습니다

 

#include <iostream>
#include <queue>
#include <functional>    // greater
using namespace std;
 
struct Student {
    int id;
    int math, eng;
    Student(int num, int m, int e) : id(num), math(m), eng(e) {}    // 생성자 정의
    // 그냥 점수에 상관 없이 학번기준 학번이 작은것이 Top 을 유지 한다
    bool operator<(const Student s) const {
        return this->id > s.id;
    }
};
 
int main() {
    priority_queue<Student> pq;  
 
    pq.push(Student(3, 100, 50));
    pq.push(Student(1, 60, 50));
    pq.push(Student(2, 80, 50));
    pq.push(Student(4, 90, 50));
    pq.push(Student(5, 70, 40));
    // 학번을 기준으로 작은 것이 먼저 출력이 된다 그 이유는 구조체 내부의 연산자 오버로딩에 있다
    while (!pq.empty()) {
        Student ts = pq.top(); pq.pop();
        cout << "(학번, 수학 , 영어 ) : " << ts.id << ' ' << ts.math << ' ' << ts.eng << '\n';
    }
 
    return 0;
}

 

 

5.  cmp 구조체 활용

이번에는 조금은 다른 방식이지만 학번이 큰 것이 Top을 유지하도록 해보겠습니다 

밑에 부분은 위에서 살펴본 코드와 거의 유사하지만 less<int> 부분만 바뀌었습니다 

 

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

 

기본적인 자료형인 int 형을 원소로 쓰고자 한다면 priority_queue<int> pq 와  같이 선언을 하지만 사실은 위에서와 같이 저런 부분이 숨겨져 있는 것입니다. less<int> 부분을 내가 원하는 기준을 설정한다면 우선순위를 조작할 수 있습니다.구조체 cmp를 less <int> 부분에 넣어 주기만 하면 간단합니다 그리고 우리가 사용하는 원소는 Student 타입이겠죠!? 그래서 main 함수 내부에 우선순위 큐 선언 부분을 priority_queue<Student, vector<Student>, cmp> pq;  로 선언을 한 것입니다

 

#include <iostream>
#include <queue>
#include <functional>    // greater
using namespace std;
 
struct Student {
    int id;
    int math, eng;
    Student(int num, int m, int e) : id(num), math(m), eng(e) {}    // 생성자 정의
};
 
// 학번을 기준으로 학번(id) 값이 큰 것이 Top 을 유지 하도록 한다.
struct cmp {
    bool operator()(Student a, Student b) {
        return a.id < b.id;
    }
};
 
int main() {
    // 위에서 만든 cmp 구조체를 넣어 준다.
    priority_queue<Student, vector<Student>, cmp> pq;  
 
 
    pq.push(Student(3, 100, 50));
    pq.push(Student(1, 60, 50));
    pq.push(Student(2, 80, 50));
    pq.push(Student(4, 90, 50));
    pq.push(Student(5, 70, 40));
    
    while (!pq.empty()) {
        Student ts = pq.top(); pq.pop();
        cout << "(학번, 수학 , 영어 ) : " << ts.id << ' ' << ts.math << ' ' << ts.eng << '\n';
    }
 
    return 0;
}