[자료구조 / C++] 우선순위 큐 (Priority Queue)란?

▶ 우선순위 큐(Priority Queue)란?

우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
-> 데이터를 우선순위에 따라 처리하고 싶을 경우 사용

자료구조	추출 데이터
스택(Stack)	가장 마지막에 삽입된 데이터
큐(Queue)	가장 먼저 삽입된 데이터
우선순위 큐(Priority Queue)	가장 우선순위가 높은 데이터

 

▶ 구현 방법

1. 리스트를 이용하여 구현
2. 힙(Heap)을 이용하여 구현

구현 방법	삽입 시간	삭제 시간
리스트	O(1)	O(N)
힙(Heap)	O(logN)	O(logN)

N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업만으로도 정렬이 수행됨
- 이 경우의 시간 복잡도는 O(NlogN)

 

▶ 기본 메소드

˙push() : 우선순위 큐에 원소 추가
˙pop() : 우선순위 큐에서 맨 앞의 원소 제거
˙top() : 우선순위 큐에서 맨 앞에 있는 원소(우선순위가 높은 원소)를 반환
˙empty() : 우선순위 큐가 비어있을 경우 True, 그렇지 않을 경우 False 반환
˙size() : 우선순위 큐에 포함되어 있는 원소의 수를 반환

 

▶ 우선순위 큐(Priority Queue) 선언 방법

<queue> 라이브러리에서 지원

#include <queue>

 

1. priority_queue<자료형, container, 비교함수> 변수명

priority_queue<type, vector<type>, custom> name;

- 비교함수에 따라 우선순위 큐를 정렬하는 선언 방식

 

2. priority_queue<자료형> 변수명

priority_queue<type> name;

- 내림차순으로 우선순위 큐를 정렬하는 선언 방식

 

3. priority_queue<자료형, greater<int>> 변수명

priority_queue<type,greater<type>> name;

- 오름차순으로 우선순위 큐를 정렬하는 선언 방식

 

선언 예시

#include <iostream>
#include <queue>

using namespace std;

int main() {
	priority_queue<int> pq;

	if (pq.empty())	//우선순위 큐가 비어있을 경우 true, 아닐 경우 false를 반환
		cout << "비어있습니다." << endl;
	else
		cout << pq.top() << endl;
}

 

위 코드 실행 결과

↑위를 통해 우선순위 큐 변수를 선언만 했을 경우, 우선순위 큐는 기본적으로 비어있는 것을 확인

 

▶ 사용 예시

1. 일반적인 선언

#include <iostream>
#include <queue>

using namespace std;

int main() {
	priority_queue<int, vector<int>, greater<int>> pq;	//오름차순 우선순위 큐 선언
	priority_queue<int> ipq;	//내림차순 우선순위 큐 선언

	pq.push(1);
	pq.push(9);
	pq.push(5);
	//우선순위 큐 변수 pq에 1, 9, 5 입력
	ipq.push(3);
	ipq.push(7);
	ipq.push(1);
	//우선순위 큐 변수 ipq에 3, 7, 1 입력

	while (pq.size()) {		//모든 원소를 출력 후 삭제하면 size가 0이 되며 반복문을 탈출하지 않을까?
		cout << pq.top();	//맨 앞의 원소를 출력
		pq.pop();	//맨 앞의 원소 삭제
	}

	cout << endl;

	while (ipq.size()) {
		cout << ipq.top();
		ipq.pop();
	}
}

실행결과

↑위 코드를 통해 우선순위 큐 변수에 원소를 입력만 해도 자동으로 정렬이 되는 것 확인/반복문 조건으로 pq.size() 대신 !pq.empty()를 사용가능할 듯

2. 배열의 범위로 선언

#include <iostream>
#include <queue>

using namespace std;

int main() {
	int Array[] = { 2, 4, 6, 3, 5, 7 };
	priority_queue<int> pq(Array, Array + 6);	//이런식의 선언도 가능하다고 함

	while (!pq.empty()) {		//우선순위 큐가 비어있으면 반복문 탈출
		cout << pq.top();
		pq.pop();
	}
}

 

실행결과

↑위 코드를 통해 배열의 범위로 우선순위 큐를 선언해 정렬하는 것도 가능한 것을 알 수 있음

 

감사합니다.

[참고] https://blog.naver.com/soojin_2604/222356481253 / https://youtu.be/AjFlp951nz0