실전 알고리즘 0x17강 - 우선순위 큐

우선순위 큐

[ 정의와 성질 ]

- pop을 할 때 가장 먼저 들어온 원소가 나오는 대신 우선순위가 가장 높은 원소가 나오는 큐

1. 원소의 추가가 O(log N)

2. 우선순위가 가장 높은 원소의 확인이 O(1)

3. 우선순위가 가장 높은 원소의 제거가 O(log N)

- 배열로 구현하면 세 연산의 시간 복잡도가 각각 O(1), O(N), O(N)이 된다.

- 힙을 이용한다.

 

[ 기능과 구현 ]

- 힙은 이진트리 모양을 가지고 있다.

- 이진 검색 트리와 다른 자료구조이다.

- 최대 힙, 최소 힙이 있고 최소 힙의 경우 루트가 최솟값이 되고 작은 값을 왼쪽부터 채워나가기 때문에 이진 검색 트리와 다르게 불균형이 발생하지 않는다.

 

- Insert : 부모 노드와 비교하여 조건에 맞게 바꾸는걸 루트까지 반복한다.

- Fetch : 최솟값은 루트의 값을 확인하면 된다. ( 10번째로 작은값은 찾을 수 없다. )

- Erase : 최솟값을 지우려면 가장 마지막 위치의 값과 바꾸고 제거한다. 이후에 루트와 자식 중 최솟값을 루트로 바꾸고 바꾼 값과 그 자식들과 비교하여 조건이 위배되지 않을 때까지 반복한다. 

 

- 이진 트리 구조를 코드로 표현하는 방법은 각 원소를 배열로 대응시켜서 만들 수 있다.

- x번지의 왼쪽, 오른쪽 자식 : 2x, 2x+1

- x번지의 부모 : x/2

- 이진 검색 트리는 배열로 대응시켜서 만들 수 없다. 연산을 수행하면 시간 복잡도가 이상해진다.

 

[ STL priority_queue ]

- reference : https://m.cplusplus.com/reference/queue/priority_queue/

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	priority_queue<int> pq; // 최대 힙
	// priority_queue<int, vector<int>, greater<int>> 로 선언시 최소 힙
	pq.push(10); pq.push(2); pq.push(5); pq.push(9); // {10, 2, 5, 9}
	cout << pq.top() << '\n'; //10
	pq.pop(); // {2, 5, 9}
	cout << pq.size() << '\n'; // 3
	if (pq.empty()) cout << "PQ is empty\n";
	else cout << "PQ is not empty()\n";
	pq.pop(); // {2, 5}
	cout << pq.top() << '\n'; // 5
	pq.push(5); pq.push(15); // {2, 5, 5, 15}
	cout << pq.top() << '\n'; // 15
}

- priority_queue에서 할 수 있는건 어차피 set에서도 할 수 있고 시간 복잡도도 동일한데 쓰는 이유는 set보다 수행 속도가 빠르고, 공간도 적게 차지하기 때문이다. 같은 연산에서 2~4배 정도 priority_queue가 빠르다.

 

[ 연습문제 ]

- 백준 11286번 : https://www.acmicpc.net/problem/11286

- 백준 1715번 : https://www.acmicpc.net/problem/1715

허프만 코딩을 이용하여 그리디 풀이로 푼다. (작은 값부터 처리하는 최소 거리 알고리즘)