[C++] STL Priority_Queue 우선순위 큐 사용법

우선순위 큐를 사용해야 하는 문제가 나올 때 사용법을 자주 검색해왔어서 개인 기록 겸 공부를 위해 정리해 보았다. 특히나 구조체나 클래스의 객체 타입을 우선순위 큐에 저장하거나, 비교 함수를 재정의, 연산자 오버 로딩도 알아보려고 한다.

 

 

0. Priority_queue(우선순위 큐) 란?

기본적으로 큐(queue)는 선입선출 FIFO(First In First Out)을 뜻한다. 때문에 우선순위 큐는 일반적인 큐와 비슷한 연산을 갖고있지만 내부 구조는 완전히 다르다. 선입선출인 큐는 pop을 하면 가장 먼저 들어왔던 원소를 반환하지만 우선순위 큐에서는 제일 우선순위가 높은 원소를 반환한다.

 

우선순위 큐는 들어간 순서에 상관없에 우선순위가 높은 데이터가 먼저 나온다.

 

우선순위 큐의 속성

1. 모든 항목에는 우선순위가 있다.
2. 우선 순위가 높은 요소는 우선 순위가 낮은 요소보다 먼저 큐에서 제외된다.
3. 두 요소의 우선 순위가 같으면 큐의 순서에 따라 제공된다.

우선순위 큐는 Container의 한 종류이며 내부적으로 Heap의 자료구조를 가지고 있다.

 

1. 기본 사용법

1.1 헤더

우선순위 큐는 queue를 include 하면 사용할 수 있다.

#include <queue>

 

1.2 멤버 함수

이름에 queue가 들어가는 만큼 queue와 멤버 함수는 거의 비슷하다.

 

• empty() : pq가 비어있으면 1, 비어있지 않으면 0을 출력한다.
• size() : pq의 크기를 출력한다.
• top() : pq에 가장 우선순위가 높은 값을 출력한다.
• push(1) : pq에 1을 우선순위에 따라 알맞은 위치에 삽입한다.
• emplace(1) : pq에 1 구조를 우선순위에 따라 알맞은 위치에 삽입한다. (push와 비슷하지만 다름)
• pop() : pq에 가장 우선순위가 높은 값을 제거한다.
• swap() : 두개의 pq 내부를 서로 바꾼다.

 

1.2.1 push와 emplace 차이

 

push는 단순히 queue에 값을 넣어준다. 때문에 오브젝트 형태를 띄울경우 복사 후 삽입해야 하므로 불필요한 복사가 늘어난다.

 

emplace는 오브젝트를 생성하지 않고 바로 값을 넣는다. 즉 copy와 constructor가 합쳐진 것이라 볼 수 있다.

 

예시 코드

#include <iostream>
#include <queue> //우선순위 큐를 위한 라이브러리
using namespace std;

int main()
{
	priority_queue<pair<char, int>> pq; // pair를 요소로 갖는 우선순위 큐 선언
    
    pq.emplace('a', 24); // pair의 오브젝트를 만들지 않고 바로 값을 push한다.
    
    // pq.push('b', 25); 이와 같은 명령어는 오류가 난다.
    
    // push를 사용할 때는 pair를 만들어 준 다음에 넣어야 한다. 이 과정에서 불필요한 복사가 일어난다.
    pq.push(make_pair('b', 25));
    
    // 우선순위 큐 출력부분
    while (!pq.empty())
    {
    	pair p = pq.top();
        cout << p.first >> " " << p.second << endl;
        pq.pop();
    }
    
    // 출력 결과
    // b 25
    // a 24
    
    return 0;
}

 

2. 우선순위 큐 활용

 

2.1 우선순위 큐 기본형

기본적으로 우선순위 큐는  다음과 같이 선언할 수 있다.

#include <queue>

//priority_queue<자료형, 컨테이너, 비교연산자> pq;
priority_queue<int, vector<int>, less<int>> pq2;
priority_queue<int> pq3;

// pq2와 pq3는 같다.

컨테이너와 비교연산자를 생략하면 기본적으로 vector와 오름차순인 less를 default로 받는다. 때문에 위의 pair형 pq에서도

{a, 24} , {b, 25} 순서로 있었기 때문에 pop을 할 경우 {b, 25}가 먼저 제거되게 된다.

 

만약 작은수 부터 출력(내림차순)을 하고싶다면 비교연산자에 greater<자료형>을 사용하면 된다.

#include <queue>

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

 

2.2 비교연산자 활용

비교연산자를 오름차순, 내림차순형이 아닌 직접 정의해주고 싶을 때 구조체와 연산자 오버로딩을 활용할 수 있다.

 

예시 - BOJ 11286 문제

https://www.acmicpc.net/submit/11286/62069522

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;

struct cmp 
{
	bool operator()(int a, int b) // 연산자 오버로딩
	{
		if (abs(a) == abs(b)) // 절댓값 a와 절댓값 b가 같다면 작은값(마이너스)를 top으로
			return a > b;
		return abs(a) > abs(b); // 절댓값이 작은값을 top으로
	}
};

int N;
priority_queue<int, vector<int>, cmp> pq; // 비교연산자 구조체형의 cmp

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;
	int temp;
	for (int i = 0; i < N; i++)
	{
		cin >> temp;
		if (temp == 0)
		{
			if (pq.empty())
			{
				cout << 0 << '\n';
				continue;
			}
			cout << pq.top() << '\n';
			pq.pop();
		}
		else
		{
			pq.push(temp);
		}
	}

	return 0;
}

 

2.3 구조체 활용

우선순위 큐를 제대로 활용하기 위해 보통 다음과 같이 구조체를(다른 컨테이너의 방법으로 사용해도 무방) 이용하여 많이 사용한다.

 

#include <queue>
#include <vector>
#include <iostream>
using namespace std;

//사용할 구조체
struct s{
  int i;
  char c;
  
  //생성자
  s(int num, char alpha) : i(num), c(alpha) {}
};

// 비교를 위한 기준
struct cmp {
  bool operator()(s a, s b) {
    // int형의 값이 같을 경우
    if(a.i == b.i) {
      // char형의 값이 큰 것이 우선하도록한다.
      return a.c < b.c;
    }
    // int형의 값이 작은 것이 우선하도록한다.
    return a.i > b.i;
  }
};

int main() {
  //우선순위큐를 선언할때 <자료형, 구현체, 비교연산자> 로 선언한다.
  priority_queue <s, vector<s>, cmp> pq;
  
  //생성자를 이용한 구조체 입력
  pq.push(s(3, 'a'));
  pq.push(s(4, 'b'));
  pq.push(s(5, 'y'));
  pq.push(s(3, 'z'));
  pq.push(s(100, 'z'));

  while(!pq.empty()) {
    s temp = pq.top();
    cout << temp.i << " " << temp.c << endl;
    pq.pop();
  }
// 출력결과
// 3 z
// 3 a
// 4 b
// 5 y
// 100 z
  return 0;
}

숫자가 작은 수가 top이 되고, 숫자가 같을 경우 알파벳이 큰 것이 top이 되도록 되어있다.

 

3. 참고 및 출처

C++ STL priority_queue 우선순위 큐 사용법(https://jungeu1509.github.io/algorithm/use-priorityqueue/)

[C++] [STL] Priority_queue (feat. 여러 기준으로 우선순위 큐 구현해보기) (https://zoosso.tistory.com/993)