[c++] STL priority_queue 우선순위 큐

c++ STL 중 하나인 우선순위 큐에 대해 알아보자.

큐와 동일하지만 안에서 정렬이 된다는 점이 다르다.

 

- 헤더는 #include <queue>

- 선언은 priority_queue<자료형, 구현체(container), 비교연산자(compare 함수)> pq 

 - 자료형은 int, double, class

 - 구현체는 기본적으로 vector<자료형>

- 비교연산자의 기본값은 less 내림차순, greater 오름차순 정렬 가능

- push/pop을 하는 경우 시간 복잡도는 logN

- 자료형이 pair<a,b>라면 우선적으로 a를 확인하고 a가 같으면 b에 따라 결정된다.

 

-pq.push(input)

-pq.pop()

-pq.top() : front 없음. iterator없음

-pq.empty()

-pq.size()

 

#include <queue>
#include <vector>
#include <map>
#define pi pair<int, int>


int main(void){

	priority_queue<pi, vector<pi>, greater<pi>> pq;
    
    map<int, int> m;
    
    for(auto i=m.begin(); i!=m.end(); i++){
    	pq.push({i->first, i->second});
    }
    
    //queue와 동일하게 iterator가 없다. 접근 시에는 top을 사용해야 함
    while(!pq.empty()){
    
   		cout<<pq.top().first<<" "<<pq.top().second;
    	pq.pop();
    }

}

 

소팅하기

 

- 기본형인 priority_queue<int> pq는 max 힙과 동일하다.

- priority_queue<int, vector<int>, less<int>> pq도 max heap

- priority_queue<int, vector<int>, greater<int>> pq는 min heap이다.

#include <stdio.h>
#include <queue>

using namespace std;

priority_queue<int> pq;                             // max heap과 동일
priority_queue<int, vector<int>, less<int>> pql;    //max heap과 동일
priority_queue<int, vector<int>, greater<int>> pqg; //min heap과 동일
int main(void)
{
  int arr[10] = {3, 4, 5, 2, 6, 7, 8, 9, 1, 10};

  for (int i = 0; i < 10; i++)
  {
    pq.push(arr[i]);
    pql.push(arr[i]);
    pqg.push(arr[i]);
  }

  printf("max heap: ");
  while (!pq.empty())
  {
    printf("%d ", pq.top());
    pq.pop();
  }
  //결과 max heap: 10 9 8 7 6 5 4 3 2 1 
  
  printf("\nmax heap2: ");
  while (!pql.empty())
  {
    printf("%d ", pql.top());
    pql.pop();
  }
  //결과 max heap2: 10 9 8 7 6 5 4 3 2 1 
  
  printf("\nmin heap: ");
  while (!pqg.empty())
  {
    printf("%d ", pqg.top());
    pqg.pop();
  }
 //결과 min heap: 1 2 3 4 5 6 7 8 9 10 
  return 0;
}

 

원하는 대로 소팅하기

구조체를 선언한 경우 그에 맞게 개별 소팅이 필요한 경우가 있다. 구조체를 사용하면 두 가지 방법으로 소팅이 가능하다.

 

구조체 예시

struct p
{
  int idx, row, col, day, hurry;
};

 

1. bool operator< 정의

bool operator<(const p &t1, const p &t2)
{
  if (t1.day == t2.day)
  {
    if (t1.hurry == t2.hurry)
    {
      return t1.row > t2.row;
    }
    return t1.hurry < t2.hurry;
  }
  return t1.day < t2.day;
}

priority_queue<p> pq;

 

 

2. struct cmp 정의

struct cmp
{
  bool operator()(p &t1, p &t2)
  {
    if (t1.day == t2.day)
    {
      if (t1.hurry == t2.hurry)
      {
        return t1.row > t2.row;
      }
      return t1.hurry < t2.hurry;
    }
    return t1.day < t2.day;
  }
};

priority_queue<p, vector<p>, cmp> pq;

 

이런 식으로 정의해서 사용하면 된다.

<, > 부호가 헷갈리는데 <는 내림차순, >는 오름차순이다.