[STL] priority_queue

목표1: STL 중 하나인 priority_queue 를 이용하여 max heap, min heap 구현
목표2: priority_queue를 사용자 정의대로 정렬하는 방법알기, 연산자 오버로딩 기초

priority_queue란?

max heap 이라는 자료구조를 배웠다면, 우선순위 큐에 대해 들어봤을 것입니다.
heap은 정렬된 트리이며, max heap은 root에 트리 안에 있는 노드 중 가장 큰 값이 있습니다.

선언

#include <queue>
using namespace std;
priority_queue<int> pq;

우선순위큐는 queue 라이브러리에 있고, std 네임스페이스 안에 정의되어 있습니다.

기능

#include <iostream>
#include <queue>
using namespace std;
priority_queue<int> pq;

int main() {
    pq.push(1);
    cout << pq.top() << endl;
    pq.push(2);
    pq.push(5);
    pq.pop();

    return 0;
}

• push
• pop
• empty
• size
• top
  등의 method가 있습니다.

출력

void print_pq (priority_queue<int> & pq){
    priority_queue<int> new_pq = pq;
    while(!new_pq.empty()){
        printf("%d ", new_pq.top());
        new_pq.pop();
    }
    printf('\n');
}

STL 에서 container adaptor 중 하나인 priority_queue는
출력시 모든 값을 다 빼야 한다는 단점이 있습니다.
그래서 저는 원본을 지키기위해 복사해놓고 출력하는 함수를 만들었습니다.

정렬 옵션 바꿔보기

priority_queue<int> pq;

 

이와 같이 정의하면 Max heap이 됩니다. 즉, top을 이용해서 출력해보시면, 내림차순으로 큰값부터 작은값이 정렬되어 나옵니다.

priority_queue 는 실제로 vector 클래스로 구현이 되어있기 때문에 vector 배열안에 맨 첫번째 원소는 이 벡터 안 원소 중 가장 큰 값일 것입니다.

그 후 만약 pop을 하면, 일련의 과정을 거쳐 다음으로 큰 수를 vector의 맨 앞에 저장하겠지요.
일련의 과정은 자료구조시간에 배웠을 것입니다~ reheapup을 이용합니다~

하지만 오름차순으로 정렬하고 싶다면?

class Compare{
public:
    bool operator() (int lhs, int rhs){
        return lhs > rhs;
    }
};

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

다음과 같이 작성하시면 되겠습니다.

또는 c++에서는 STL 컨테이너들을 잘 활용할 수 있도록 연산자도 제공하고있습니다.
그래서 아래와 같이 아주 쉽게 작성할 수 있습니다.

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

default는 less입니다. (내림차순이 됨)

 

 

 

우리는 사용자 정의 함수를 이용해서 응용문제를 풀어봅시다.

백준 11286 절댓값 힙

https://www.acmicpc.net/problem/11286

#include <cmath>

class Compare{
public:
    bool operator () (const int & lhs, const int & rhs){
        if (abs(lhs) == abs(rhs)) return lhs > rhs;
        return abs(lhs) > abs(rhs);
    }
};

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

위 사용자 정의 함수를 만들어서 문제를 풀 수 있습니다.