C++ STL priority_queue 우선순위큐

0. 우선순위 큐(priority Queue)란?

Priority Queue는 Container의 한 종류이며

일반 queue는 First In First Out인 것에 반해 

설정된 우선순위에 따라 우선순위가 가장 큰 것이 Top을 유지하고 먼저 Out(pop)된다.

내부적으로는 Heap의 자료구조를 갖고있다.

 

1. 기본 사용법 

1.1 헤더

우선순위 큐는 queue를 include 하여 사용한다.

#include <queue>

 

1.2 선언

priority_queue<자료형, 컨테이너, 비교연산자> pq;

구현체와 비교연산자는 각각 vector와 less<T>가 default 값이다.

자료형 : int, double등 기본 자료형 뿐만 아니라 구조체, 클래스 등 다양하게 사용 가능

컨테이너 : 요소를 저장하는데 사용할 기본 컨테이너 유형. (보통 vector)

비교연산자 : 우선순위를 정하는 비교 기준

 

1.3 멤버함수

Element access

 top : priority queue 내부의 제일 우선순위의 값을 보여준다.

 

Capacity 

empty : priority queue가 비었는지 확인한다. 비었으면 true, 비지 않았으면 false를 반환

size : priority queue의 요소의 수를 반환한다.

 

Modifiers

push : 요소를 삽입하고 priority queue(container)를 정렬한다.

emplace : priority의 요소를 구성한다.(구조 삽입)

pop :  top element를 제거한다.

swap : 두개의 priority queue를 swap한다. (내부를 서로 바꾼다.)

 

1.3.1 push와 emplace의 차이

우선순위 큐의 경우 구조체를 많이 삽입하게 되는데 push에 경우 단순히 queue에 값을 넣어준다.

다시 말하면 오브젝트로 제작 후 삽입해야하므로 불필요한 복사가 많이 일어난다. 

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

cpprefence에선 emplace를 제자리에 요소를 구성하여 컨테이너를 정렬한다고 언급했다.

 

1.3.2 예시코드

#include <queue> //queue를 사용하기 위한 라이브러리
#include <iostream> //cout을 std:: 없이 사용하기 위한 라이브러리
#include <vector> // vector사용을 위한 라이브러리
#include <algorithm> 
#include <utility>

using namespace std;

priority_queue<pair<char, int>>pq;
int main() {

	//pair 오브젝트를 만들지 않고 바로 값을 push한다.
	pq.emplace('a', 24); 
	
	//pq.push('v', 30);  //개체 형식이 pair이므로 오류남

	pq.push(make_pair('v', 25));

	//우선순위 큐 출력
	while (!pq.empty()) {
		pair<char,int> p= pq.top();
		cout << p.first << " " << p.second << "\n";
		pq.pop();
	}

	return 0;
}
	//  출력결과
	//	v 25
	//	a 24

1.4 자료구조 힙

우선순위 큐는 보통 힙으로 구현된다. 그래서 top이 최댓값인 우선순위 큐를 최대 힙, 최솟값인 우선순위 큐를 최소 힙이라고 부르기도 한다.

 

1.4.1 구조

힙의 구조는 이진트리이며 정확히는 완전 이진 트리이다. 

제일 먼저 pop이나 top연산을 하면 빠져나오는 원소는 루트 원소이다.

 

1.4.2 연산과정

1. 완전 이진 트리 형태를 유지하는 첫번째 원소 자리에 원소를 삽입하고
2. 부모와 우선순위를 비교하여
3. 부모가 우선순위가 낮으면 자리를 바꾼다.
4. 2,3 과정을 반복해 본인의 자리를 차지하고 연산을 종료한다.

 

1.4.3 시간복잡도

힙은 완전 이진 트리의 형태이기 때문에 반드시 균형 트리이고,

따라서 원소의 개수가 N개면 자리를 바꾸는 횟수는 최대 높이, 즉 O(log N)번만 수행되므로

push의 시간복잡도는 O(log N)이다.

 

1.4.4 힙 구현

배열을 사용하여 힙을 구현할 때는 루트를 1번 인덱스로 시작하여서

정점 i의 부모의 인덱스는 i/2이고(정수 자리 내림), 왼쪽 자식 노드의 인덱스는 i*2, 오른쪽 자식 노드의 i*2+1이라는 점으로

부모와 자식을 찾아가기가 매우 수월해진다.

 

2.예시

2.1 간단한 Priority queue 예시

#include <queue> //queue를 사용하기 위한 라이브러리
#include <iostream> 
#include <algorithm> 

using namespace std;

priority_queue<int>pq;

int main() {

	pq.push(5);
	pq.push(3);
	pq.push(1);
	pq.push(2);
	pq.push(6);
	pq.push(4);

	//우선순위 큐 출력
	while (!pq.empty()) {
		cout << pq.top() << "\n";
		pq.pop();
	}
	return 0;
}

// 출력예시
//6
//5
//4
//3
//2
//1

 

3. 심화 사용법

3.1 우선순위 큐 활용 (가장 작은 것을 우선순위로 하는 방법)

구조체 등을 컨테이너로 지정하거나 비교연산자에 less, greater같은 비교연산자를 사용하여 우선순위 큐를 활용할 수 있다. 

우선순위 큐를 작은 값을 우선으로 배치하게 하려면 다음과 같은 방법이 있다.

 

3.1.1 음수활용

 원소를 넣을 때 음수로 변환해서 넣게 되면 가장 큰 값이 TOP을 유지하는 특성상  절댓값이 가장 작은 값이 TOP을 유지하게 될 것이다  출력할 때만 음수를 양수로 치환해주면 비교연산자 사용없이 작은 값을 우선으로 하는 priority queue를 만들 수 있다.

int main() {

	pq.push(-5);
	pq.push(-3);
	pq.push(-1);
	pq.push(-2);
	pq.push(-6);
	pq.push(-4);

	//우선순위 큐 출력
	while (!pq.empty()) {
		int a = -pq.top();
		cout << a << "\n";
		pq.pop();
	}
	return 0;
}

*/
출력
1
2
3
4
5
6
*/

 

3.1.2 기본 비교연산자 활용

priority_queue<자료형, 구현체, 비교연산자> pq;

비교연산자는 default값으로 less<자료형>을 갖는다. 

비교연산자를 greater<자료형>으로 넣어서 priority queue를 선언한다면 작은 값을 우선으로 하는 pq를 만들 수 있다.

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

 

3.2 구조체 활용

우선순위 큐를 제대로 활용하기 위해 구조체를 많이 사용한다. 

#include <queue> //queue를 사용하기 위한 라이브러리
#include <iostream> //cout을 std:: 없이 사용하기 위한 라이브러리
#include <vector> // vector사용을 위한 라이브러리
#include <algorithm> 
#include <utility>

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) {
		if (a.i == b.i) { //int형 값이 같으면 char값이 큰것 우선
			return a.c < b.c;
		}
		return a.i > b.i; //int형 값이 작은 것 우선
	}
};

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

int main() {

	pq.push(s(5,'a'));
	pq.push(s(5,'k'));
	pq.push(s(7,'c'));
	pq.push(s(3,'c'));
	pq.push(s(5, 'c'));
	pq.emplace(7,'z');

	//우선순위 큐 출력
	while (!pq.empty()) {
		s temp = pq.top();
		cout << temp.i <<" "<<temp.c <<"\n";
		pq.pop();
	}
	return 0;
}

//출력값
//3 c
//5 k
//5 c
//5 a
//7 z
//7 c

 

 

 

출처

• https://m.blog.naver.com/kks227/220791188929
• https://jungeu1509.github.io/algorithm/use-priorityqueue/  
• https://en.cppreference.com/w/cpp/container/priority_queue