C++ STL priority_queue

• 우선순위 큐(priority queue)란 선입선출식(FIFO, First In First Out)으로 작동하는 일반적인 큐(queue)와는 다르게, 우선순위가 높은 원소 순으로 나가게 됩니다. (자세한 원리는 자료구조의 힙을 참조하시면 이해하기 쉽습니다.)
• C++에서 우선순위 큐 컨테이너는 <queue> 헤더 안에 있기 때문에 큐와 마찬가지로 <queue> 헤더를 포함해야 합니다.
• 우선순위 큐를 선언할 때에는 기본적으로 컨테이너에 들어갈 원소의 타입을 명시해야 하며, 우선순위 큐의 컨테이너와 비교변수도 명시할 수 있습니다. (명시하지 않을 경우 기본적으로 내림차순으로 정렬됩니다.)
• char나 string 타입의 경우 기본적으로 아스키코드값에 따라 정렬되며, 아래에서 소개할 비교변수 생성을 통하여 임의로 정렬할 수 있습니다.

#include <queue>
std::priority_queue<type> pq1; // namespace std 사용 시 std 생략가능
std::priority_queue<int> pq2; // 기본적으로 내림차순으로 정렬, less<int>와 동일
std::priority_queue<int, vector<int>, greater<int> > pq2; // 오름차순 정렬

 

 

<priority_queue의 멤버 함수>

-std::priority_queue<int> q; 와 int element; 로 선언되어 있다고 가정합니다-

 

 1) 삽입과 삭제

pq.push(element);

-> priority_queue에 원소 element를 추가합니다.

 

pq.pop();

-> priority_queue에서 우선순위가 가장 높은 원소를 제거합니다.

 

 

 2) 원소 참조

pq.top();

-> priority_queue에서 우선순위가 가장 높은 원소를 참조합니다.

 

 

 3) 사이즈 관련

pq.size();

-> priority_queue의 크기를 리턴합니다.

 

pq.empty();

-> priority_queue가 비어있는 지 확인합니다. 비어있으면 1, 그렇지 않으면 0을 리턴합니다.

 

 

 

<구조체나 클래스를 이용한 비교변수 생성>

 C++에서 기본적으로 제공하는 비교함수만 가지고 우선순위 큐를 사용할 수도 있지만, 보통은 프로그래머가 임의로 비교변수를 생성하여 사용하는 것이 일반적입니다. 

#include <iostream>
using namespace std;

struct compare1 {
    bool operator()(int a, int b) { // 내림차순
        return a < b;
    }
};

struct compare2 {
    bool operator()(char c1, char c2) {
        // 문자가 's'인 경우 우선
        if(a == 's')
            return 0;
        else if(b == 's')
            return 1;
        // 그외는 아스키코드 내림차순
        return a > b;
    }
};

int main() {
    // priority_queue<int>와 기능적으로 동일
    priority_queue<int, vector<int>, compare1> pq1;
    
    // 문자 's'에 우선순위를 가지는 우선순위 큐
    priority_queue<char, vector<char>, compare2> pq2;
    pq2.push('c');
    pq2.push('x');
    pq2.push('s');
    pq2.push('n');
    
    // 출력: s c n x 
    while(!pq2.empty()) {
        cout << pq2.top() << '\n';
        pq2.pop();
    }
    
    return 0;
}

 위와 같이 구조체의 내부 연산자(operator) 오버로딩을 통하여 임의로 우선순위 설정을 할 수 있습니다. 개인적으로는 operator 함수의 매개변수 중 좌변을 0(false), 우변을 1(true)로 상정하고 설계하는 것이 도움이 되었습니다.

 

 또는 아래와 같이 클래스를 생성하고 연산자 오버로딩을 이용하여 우선순위 큐를 더욱 효율적으로 사용할 수 있습니다. (클래스에 관한 기본내용은 클래스 사용법에서 확인할 수 있습니다.)

#include <iostream>
#include <queue>
using namespace std;

// 학생들의 이름과 점수를 관리하는 Student 클래스
class Student {
private:
    string name;
    int score;
    

public:
    Student(string name, int score) {
        this->name = name;
        this->score = score;
    }

    bool operator<(Student s) const;
    string getName() {
        return this->name;
    }
    int getScore() {
        return this->score;
    }
};

// 비교 연산자 오버로딩
bool Student::operator<(Student s) const {
    if(this->score == s.score) // 점수가 같으면 알파벳 이름순대로 우선
        return this->name > s.name;
        
    // 그외에는 점수가 높은 순서대로 우선
    return this->score < s.score;
}

int main() {
    // 클래스 내부의 비교 연산자를 통하여 자동적으로 정렬됨
    priority_queue<Student> pq;
    
    pq.push(*(new Student("Mike", 90)));
    pq.push(*(new Student("Peter", 65)));
    pq.push(*(new Student("John", 77)));
    pq.push(*(new Student("James", 77)));
    
    /*
    출력:
    	Mike 90
    	James 77
        John 77
        Peter 65
    */
    while(!pq.empty()) {
        Student s = pq.top();
        cout << s.getName() << ' ' << s.getGrade() << '\n';
        pq.pop();
    }
    return 0;
}

---