[C++] priority_queue 컨테이너 사용법

Doorbals·2023년 1월 12일

cpp

CPP

목록 보기

10/16

priority_queue 컨테이너

C++에서 제공하는 우선순위 큐 자료구조.
큐에 있는 모든 원소 중에서 가장 큰 값이 top을 유지하도록 설계되어 있음.
내부적으로 Heap의 자료구조를 가짐.

1. 헤더 파일

#include <queue>

2. 멤버 함수

push() : 우선순위 큐에 원소를 삽입
pop() : top의 원소를 제거
top() : top에 있는 원소를 반환 (top == 우선순위가 가장 높은 원소)
empty() : 우선순위 큐가 비어있으면 true, 아니면 false 반환
size() : 우선순위 큐에 들어있는 원소 수 반환
emplace() : 우선순위 큐에 구조를 삽입

❗push()와 emplace()의 차이

우선순위 큐에는 구조체를 많이 삽입하게 되는데, push의 경우 오브젝트를 생성 후 삽입해야하기 때문에 불필요한 복사가 많이 발생한다.
emplace의 경우 오브젝트를 생성하지 않고 바로 값을 넣는다.

🖥️ 예제코드

int main(int argc, char** argv)
{
	priority_queue<pair<char, int>> pq;
	
	pq.push(pair<char, int>('a', 2));	// push 사용 시 pair<char, int>()로 오브젝트 생성

	pq.emplace('b', 1);		// emplace 사용 시 pair 오브젝트 만들지 않고 바로 값을 입력 

	while (!pq.empty())
	{
		cout << pq.top().first << ' ' << pq.top().second << endl;
		pq.pop();
	}
}

✔️ 출력 결과

출력 결과로 알 수 있는 또 한 가지는 pair 구조체를 삽입 시 first의 값을 기준으로 정렬된다.

3. 우선순위 큐 정렬 기준 변경

0) 우선순위 큐 선언 방법

priority_queue<'자료형', '구현체', '비교연산자'> 이름;

자료형 : int, double, pair 등 기본 자료형 및 구조체, 클래스 등을 사용한다.
구현체 : 보통 vector<자료형>으로 구현한다. 지정하지 않으면 vector로 기본 적용.
비교연산자 : 비교를 위한 기준을 알려준다.

1) 내림차순 (큰 값 먼저)

priority_queue<int> pq;

구현체, 비교연산자를 지정하지 않고 자료형만 입력하면 기본적으로 내림차순으로 정렬이 된다.

2) 오름차순 (작은 값 먼저)

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

비교연산자에 greater<int>를 사용하면 오름차순으로 정렬된다.

3) 사용자 설정

struct compare
{
	bool operator()(int a, int b)
    {
    	return a > b;	// priority_queue에 적용 시 부모 노드와 크기를 비교해 
        				// a가 b보다 크면 true를 리턴해 swap할 것
    }
}

int main()
{
	priority_queue<int, vector<int>, compare> pq;
}

직접 비교연산자를 만들고, 이를 priority_queue의 비교연산자 부분에 넣으면 해당 기준으로 정렬된다.

🖥️ 예제 코드

#include <iostream>
#include <queue>

using namespace std;

struct compare
{
	bool operator()(pair<char, int> a, pair<char, int> b)
	{
		return a.second < b.second;	// pair의 두 번째 원소(int형)의 내림차순으로 정렬
	}
};


int main(int argc, char** argv)
{
	vector<pair<char, int>> v;
	
    // ('a', 5), ('b' 4), ...와 같은 순서로 vector 초기화 
	for(int i = 0; i < 5; i++)
		v.push_back(pair<char, int>('a' + i, 5 - i));

	// 내림차순
	priority_queue<pair<char, int>> pq_max;
	
	// 오름차순
	priority_queue<pair<char, int>, vector<pair<char, int>>, greater<pair<char, int>>> pq_min;

	// 사용자 설정 (숫자 내림차순)
	priority_queue<pair<char, int>, vector<pair<char, int>>, greater<pair<char, int>>> pq_custom;
	
	// vector의 값을 priority_queue에 복사
	for (int i = 0; i < 5; i++)
	{
		pq_max.push(v[i]);
		pq_min.push(v[i]);
		pq_custom.push(v[i]);
	}

	cout << "내림차순" << endl;
	for (int i = 0; i < 5; i++)
	{
		cout << pq_max.top().first << " : " << pq_max.top().second << endl;
		pq_max.pop();
	}
	
	cout << "오름차순" << endl;
	for (int i = 0; i < 5; i++)
	{
		cout << pq_min.top().first << " : " << pq_min.top().second << endl;
		pq_min.pop();
	}
		
	cout << "사용자 설정" << endl;
	for (int i = 0; i < 5; i++)
	{
		cout << pq_custom.top().first << " : " << pq_custom.top().second << endl;
		pq_custom.pop();
	}
}