std::priority_queue

코딩 테스트를 위한 자료 구조와 알고리즘 with C++

 

 

std::priority_queue

• STL에서 제공하는 우선순위 큐 컨테이너 어댑터이다.
• 기본적으로 std::vector가 컨테이너로 사용된다.
• 기본 비교자로 std::less가 사용되며, 가장 큰 수가 가장 위에서 높은 우선 순위를 갖는 최대 힙(Max Heap)을 생성한다.
  std::greater를 사용하면 가장 작은 수가 가장 높은 우선 순위를 갖는 최소 힙(Min Heap)이 생성된다.
• 순회할 필요가 없으므로 반복자를 제공하지 않는다.
• Root 이외의 원소는 접근할 수 없다.

 

std::priority_queue의 성능

• 최대 힙에서 최대 원소, 최소 힙에서 최소 원소에 대한 접근은 O(1)에 수행된다.
• 원소의 삽입은 상향식 재구성(Bottom-up Heapify)을 거치므로 O(log n)에 수행된다.
• Root의 삭제는 하향식 재구성(Top-down Heapify)을 거치므로 O(log n)에 수행된다.
• 생성자에 전달된 초기화 리스트에 대해서는 O(n)에 수행되는 좀 더 빠른 힙 생성 알고리즘이 사용된다.
  (각각 삽입하게 되면 O(nlog n) 시간이 걸린다.)

 

#include <iostream>
#include <queue>

using namespace std;

void main()
{
    priority_queue<int> pr_que;

    // 100, 300, 200 Push
    pr_que.emplace(100);
    pr_que.emplace(300);
    pr_que.emplace(200);

    // Pop 300
    pr_que.pop();

    cout << "Top: " << pr_que.top() << endl;

    cout << "Empty: " << boolalpha << pr_que.empty() << endl;

    cout << "크기: " << pr_que.size() << endl;
}

 

출력

Top: 200
Empty: false
크기: 2