[C++] STL priority_queue 사용법

priority queue

C++ STL 컨테이너 중 하나로, 내부적으로 힙 자료구조로 구현된 우선순위 큐를 보다 편하게 사용할 수 있게 해준다. 기존의 스택이나 큐 같은 자료구조의 경우, 먼저 들어왔는지 나중에 들어왔는지 같은 인덱스가 삽입된 순서에 의거하여 구성되는 자료구조 형식이라면, 우선순위 큐는 인덱스가 삽입된 순서와는 별개로 특정한 가중치를 가지고 그 가중치에 따라 순서가 결정되는 자료구조 형식이다.

보통 C++ STL에서 사용하는 priority_queue 컨테이너의 경우엔 인덱스의 크기가 가장 큰 순서대로 top에 정렬된다. (기본은 내림차순) 만약 인덱스의 크기가 가장 작은 순서대로 top에 정렬하고 싶다면, priority_queue<int , vector, greater<int>> pq; 와 같이 정렬기준을 명시하거나 그냥 삽입할때에 음수로 변환하여 삽입하면 된다. 필자 개인적으로는 후자가 사용하기 더 용이한 것 같다. 후자의 경우 삽입되어 있는 인덱스들이 모두 음수형태로 변환되어 저장되므로, 출력할때에도 꼭 부호를 바꾸어 양수로 출력되도록 설정해주어야 한다.

다익스트라 알고리즘을 구현할때에 쓰이는 자료구조이다. 다만 이때도, 정렬기준을 오름차순으로 변경하기 위해 음수로 변경하여 삽입하고, 출력할때에도 부호를 바꿔서 출력하는 매커니즘을 사용하게 된다.

내부 함수 목록

- 우선순위 큐는 기본적으로 vector 컨테이너로 구현되어 있지만, dequeue와 함께 사용할 수도 있다.
- 정렬 기준은 기본적으로 내림차순(less<T>)이지만, 이 역시도 기준을 바꿀 수 있다.
- 기본 생성자 형식: priority_queue pq;
- 내부 컨테이너 변경: priority_queue<int, deque<int>> pq;
- 정렬 기준 변경: priority_queue<int , vector, greater<int>> pq; 

 

#include <iostream>
#include <queue>

using namespace std;

int main() {
    priority_queue<int> pq; //기본은 내림차순

    //원소 삽입
    pq.push(4);
    pq.push(7);
    pq.push(3);
    pq.push(1);
    pq.push(10);
    //가장 큰 값이 top에 오도록 자동으로 정렬된다

    cout << pq.size() << "\n"; // 5

    while (!pq.empty()) {
        cout << pq.top() << " "; // 10 7 4 3 1
        pq.pop();
    }

    return 0;
}

기본적으로 이런식으로 사용할 수 있다. 

 

#include <iostream>
#include <queue>

using namespace std;

int main() {
    priority_queue<int, vector<int>, greater<int>> pq;
    //오름차순으로 정렬기준 변경

    //원소 삽입
    pq.push(4);
    pq.push(7);
    pq.push(3);
    pq.push(1);
    pq.push(10);
    //가장 작은 값이 top에 오도록 자동으로 정렬된다

    cout << pq.size() << "\n"; // 5

    while (!pq.empty()) {
        cout << pq.top() << " "; // 1 3 4 7 10
        pq.pop();
    }

    return 0;
}

#include <iostream>
#include <queue>

using namespace std;

int main() {
  priority_queue<int> pq;

  // 음수로 변환해서 원소 삽입
  pq.push(-4);
  pq.push(-7);
  pq.push(-3);
  pq.push(-1);
  pq.push(-10);

  cout << pq.size() << "\n"; // 5

  // 절댓값이 작은 원소부터 출력되도록 (오름차순)
  while (!pq.empty()) {
      cout << -pq.top() << " "; // 1 3 4 7 10
      pq.pop();
  }

  return 0;
}

정렬기준을 기본인 내림차순에서 오름차순으로 바꾸어 저장하려면 다음과 같이 해주면 된다. 다익스트라 알고리즘 구현 시, 두번째 방식으로 우선순위큐를 사용하게 된다.