STL 우선순위 큐, Priority Queue 사용법 [C++]

 

유용한 STL인 큐 중에서

우선순위 큐를 알아보자

그냥 큐와 무엇이 다른지도 알아보자

 

Priority queues are a type of container adaptors, specifically designed such that its first element is always the greatest of the elements it contains, according to some strict weak ordering criterion.

 

일반적으로 첫번째 원소가 제일 큰 값을 가지게 하는 컨테이너다.

**물론 첫번째 원소가 제일 작은 값을 나오게 할 수도 있다.

 

This context is similar to a heap, where elements can be inserted at any moment, and only the max heap element can be retrieved (the one at the top in the priority queue).

 

그리고 힙과 아주 비슷하다.

 

즉 이것도 데이터 삽입과 정렬이 한꺼번에 일어나는데

시간복잡도 O(logN)을 가지고 있다.

 

또한 큐인 만큼 #include<queue>만 하면 된다.

 

 

선언은 이렇게 한다.

 

 

기본 함수들로는

 

기본형태

• priority_queue<T, Container, Compare>: 선언한 자료형 변수들을 Compare함수에 따라 정렬하는 큐
• priority_queue<T>: 선언한 자료형 변수들을 내림차순에 따라 정렬하는 큐

 

Insert & Delete

• push(element): 우선순위 큐에 원소 추가
• pop(): 우선순위 큐에서 top의 원소를 삭제(맨 앞의 원소를 말함)

 

Read

• top(): top에 있는 원소를 반환 (맨 앞의 원소를 말함)

 

나머지

• empty(): 비어있으면 true 아니면 false를 반환
• size(): 우선순위 큐에 포함되어 있는 원소들의 수를 반환

 

 

 

top()의 예시

// priority_queue::top
#include <iostream>       // std::cout
#include <queue>          // std::priority_queue

int main ()
{
  std::priority_queue<int> mypq;

  mypq.push(10);
  mypq.push(20);
  mypq.push(15);

  std::cout << "mypq.top() is now " << mypq.top() << '\n';

  return 0;
}

 

push&pop

// priority_queue::push/pop
#include <iostream>       // std::cout
#include <queue>          // std::priority_queue

int main ()
{
  std::priority_queue<int> mypq;

  mypq.push(30);
  mypq.push(100);
  mypq.push(25);
  mypq.push(40);

  std::cout << "Popping out elements...";
  while (!mypq.empty())
  {
     std::cout << ' ' << mypq.top();
     mypq.pop();
  }
  std::cout << '\n';

  return 0;
}
/////////////////////////
Popping out elements... 100 40 30 25

 

 

생성자, constructor

// constructing priority queues
#include <iostream>       // std::cout
#include <queue>          // std::priority_queue
#include <vector>         // std::vector
#include <functional>     // std::greater

class mycomparison
{
  bool reverse;
public:
  mycomparison(const bool& revparam=false)
    {reverse=revparam;}
  bool operator() (const int& lhs, const int&rhs) const
  {
    if (reverse) return (lhs>rhs);
    else return (lhs<rhs);
  }
};

int main ()
{
  int myints[]= {10,60,50,20};

  std::priority_queue<int> first;
  std::priority_queue<int> second (myints,myints+4);
  std::priority_queue<int, std::vector<int>, std::greater<int> >
                            third (myints,myints+4);
  // using mycomparison:
  typedef std::priority_queue<int,std::vector<int>,mycomparison> mypq_type;

  mypq_type fourth;                       // less-than comparison
  mypq_type fifth (mycomparison(true));   // greater-than comparison

  return 0;
}

 

 

그래..

그렇다면

우선순위 큐를 왜 쓸까??

 

우선순위 큐는 우선순위가 포함된 자료가 들어간다.

그러면 큐 내부에서 pop을 했을 때 가장 우선순위가 높은 자료가 먼저 나올 수 있도록 재배열한다. 

++모든 자료의 우선순위가 같다면 큐와 동일하게 작동한다.

 

바로 저 부분때문이다.

또한 바이너리 힙으로 구현되어 빠르게 정렬되고 작동한다.

 

우선순위 큐를 안다면.. 알고리즘 문제 중에 쉽게 풀 수 있는 것이 있었을 것 같다는 느낌이다.

 

---

우선순위 큐는 특히 많은 곳에 쓰이는데

데이터 압축, 허프먼 코딩 알고리즘

다익스트라 , 프림 알고리즘

K번째 작은 요소 찾기 등에 쓰인다.

 

특히 K번째 큰 값, 작은 값을 찾을 때

이러한 Max Heap, Min Heap의 구조가 최적의 구조라는 것이다.

 

---

 

참고링크

 

http://www.cplusplus.com/reference/queue/priority_queue/