[자료구조] 우선순위 큐와 힙

1. 우선순위 큐

1.1 우선순위 큐란?

큐 : 선입선출(FIFO)의 원칙에 의하여 먼저 들어온 데이터가 먼저 나가는 자료구조이다.
우선순위 큐(priority queue) : 데이터들이 우선순위를 가지고 있어 우선순위가 높은 데이터가 먼저 출력되는 자료구조이다.

우선순위 큐는 배열, 연결 리스트 등의 여러 가지 방법으로 구현이 가능하지만 가장 효율적인 구조는 힙(heap)이다.

1.2 우선순위 큐 ADT

데이터 : 우선순위를 가진 요소들의 모음
연산 :
-insert(item) : 우선순위 큐에 항목 item을 추가한다.
-remove() : 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 이 요소를 반환한다.
-find() : 우선순위가 가장 높은 요소를 삭제하지 않고 반환한다.
-isEmpty() : 우선순위 큐가 공백 상태인지를 검사한다.
-isFull() : 우선순위 큐가 포화 상태인지를 검사한다.
-display() : 우선순위 큐의 모든 요소들을 출력한다.

2. 힙

2.1 힙이란?

힙 : 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 완전 이진트리이다.

2.2 힙의 종류

• 최대 힙(max heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
  - key(부모 노드)≥key(자식 노드)
  

• 최소 힙(min heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리
  - key(부모 노드)≤key(자식 노드)
  
  

2.3 힙의 구현 방법

• 힙 트리의 노드에 차례대로 번호를 붙인다.

• 완전 이진트리이기 때문에 중간에 비어 있는 요소가 없다.

• 노드 번호를 배열의 인덱스로 생각하면 배열에 힙의 노드들을 저장할 수 있으므로 힙을 저장하는 효과적인 자료구조는 배열이다.

• 프로그램 구현을 쉽게 하기 위해 배열의 첫 번째 인덱스인 0은 사용하지 않는다.

• 트리의 모든 위치의 노드 번호는 변하지 않는다.
  

• 부모 노드와 자식 노드의 관계
  왼쪽 자식의 인덱스 = (부모의 인덱스)*2
  오른쪽 자식의 인덱스 = (부모의 인덱스)*2 +1
  부모의 인덱스 = (자식의 인덱스)/2

2.4 삽입 연산

힙에 새로운 요소가 들어오면 더 이상 힙 트리의 성질이 만족되지 않기 때문에 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시켜 주는 과정이 필요하다.

방법
1. 새로운 노드를 기존의 힙 트리의 번호순으로 가장 마지막 위치에 삽입한다.
2. 새로운 노드를 부모 노드와 비교하여 교환한다.
3. 힙의 성질을 만족시킬 때까지 2번을 반복한다.

최대 힙에서의 삽입 알고리즘

insert(key)

heapSize <- heapSize + 1;
i <- heapSize;
node[i] <- key;
while i != 1 and node[i] > node[PARENT(i)] do
	node[i] <-> node[PARENT(i)];
	i <- PARENT(i);

2.5 삭제 연산

힙에서 삭제 연산은 루트 노드를 삭제하는 것이다. 루트 노드를 삭제하고 힙의 성질을 만족시키도록 힙을 재구성한다.

방법
1. 루트 노드를 삭제하고, 마지막 노드를 루트 노드 자리로 가져온다.
2. 새로운 루트 노드와 자식 노드들을 비교하여 교환한다. (최대 힙인 경우 자식들 중 더 큰 값과 교환한다.)
3. 힙의 성질을 만족시킬 때까지 2번을 반복한다.

힙 트리에서의 삭제 알고리즘

remove()

item <- A[1];
A[1] <- A[heapSize];
heapSize <- heapSize - 1;
i <- 2;
while i <= heapSize do
	if i < heapSize and A[LEFT(i)] > A[RIGHT(i)]
		then largest <- LEFT(i);
		else largest <- RIGHT(i);
	if A[PARENT(largest)] > A[largest]
		then break;
	A[PARENT(largest)] <-> A[largest];
	i <- LEFT(largest);
return item;

3. C++로 우선순위 큐 구현

#include <queue>
#include <functional>
using namespace std;

// STL의 우선순위 큐를 이용한 내림차순 정렬, 최대힙 사용
void heapSortDec(int a[], int n) {
	priority_queue<int> maxHeap;
	for (int i = 0; i < n; i++)
		maxHeap.push(a[i]);
	// MaxHeap을 이용해 내림차순으로 정렬하기 위한 반복문
	for (int i = 0; i < n; i++) {
		a[i] = maxHeap.top();
		maxHeap.pop();
	}
}

// STL의 우선순위 큐를 이용한 오름차순 정렬, 최소힙 사용
void heapSortInc(int a[], int n) {
	priority_queue<int, vector<int>, greater<int>> minHeap;
	for (int i = 0; i < n; i++)
		minHeap.push(a[i]);
	// MinHeap을 이용해 오름차순으로 정렬하기 위한 반복문
	for (int i = 0; i < n; i++) {
		a[i] = minHeap.top();
		minHeap.pop();
	}
}

4. [예제] 백준 1966번 - 프린터 큐

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

int main() {
	int num_test_cases; // 문제 수
	int N, M; // 해당 문제의 문서 수, 관심 있는 번호
	int temp_priority; // 중요도
	int temp_order=0;

	cin >> num_test_cases;

	for (int i = 0; i < num_test_cases; i++) {
		cin >> N >> M;
		priority_queue<int> pq;
		queue<pair<int, int>> q;

		for (int j = 0; j < N; j++) {
			cin >> temp_priority;
			q.push({ j, temp_priority });
			pq.push(temp_priority);
		}

		while (!q.empty()) {
			int index = q.front().first;
			int value = q.front().second;
			q.pop();

			if (pq.top() == value) {
				pq.pop();
				++temp_order;
				if (M == index) {
					cout << temp_order << endl;
					break;
				}
			}
			else q.push({ index, value });
		}
	}
	return 0;
}