[C++] 우선순위 큐

<정의>

- 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것이다.

- 우선순위 큐는 힙(Heap)이라는 자료구조를 가지고 구현할 수있다.

 

<우선순위 큐를 Heap으로 구현하는 이유>  //우선순위 큐를 배열이나 연결리스트로 구현하지 않는 이유

1. 만약 배열로 구현한다고 가정하자. 우선순위가 높은 순서대로 배열의 가장 앞부분부터 넣는다면, 우선순위가 높은 데이터를 반환하는 것은 맨 앞의 인덱스를 바로 이용하면 되므로 어렵지 않다.

하지만 우선순위가 중간인 것이 들어가야 하는 삽입 과정에서는 뒤의 데이터까지 인덱스를 모두 한 칸씩 뒤로 밀어야 하는 단점이 있다.

최악의 경우 삽입해야 하는 위치를 찾기 위해 모든 인덱스를 탐색해야 한다. 즉 이 때의 시간 복잡도는 자료가 n개라고 할 때 O(n) 이 된다. → 배열로 구현 시 시간 복잡도 : 삭제는 O(1), 삽입은 O(n)

2. 만약 연결리스트로 구현한다고 가정하자. 이 또한 우선 순위가 높은 순서대로 연결을 시키면, 우선순위가 높은 데이터의 반환은 배열과 마찬가지로 쉽다.

하지만 연결리스트 또한 삽입의 과정 또한 배열과 마찬가지로 그 위치를 찾아야 한다. 최악의 경우 맨 끝에까지 가게 된다. → 연결리스트로 구현 시 시간 복잡도 : 삭제는 O(1), 삽입은 O(n)

3. 우선순위 큐를 힙으로 구현한다고 가정하자. 힙의 경우 삭제나 삽입 과정에서 모두 부모와 자식 간의 비교만 계속 이루어진다. 

즉, 이진 트리의 높이가 하나 증가할 때마다 저장 가능한 자료의 갯수는 2배 증가하며, 비교 연산 횟수는 1회 증가한다. 즉 삭제나 삽입 모두 최악의 경우에는 O(log2n) 의 시간 복잡도를 가진다. → 힙으로 구현 시 시간 복잡도 : 삭제는 O(log2n), 삽입은 O(log2n)

이처럼 배열이나 연결 리스트가 삭제에서는 시간 복잡도의 우위를 점할지라도, 삽입의 시간 복잡도가 힙 기반이 월등하기 때문에, 편차가 심한 배열과 연결리스트보다는 힙으로 구현하는 것이다.

 

<소스코드>

- Priority_queue; 를 간단히 설명하자면 heap으로 구성된 queue로 항상 최대값 혹은 최소값이 root에 있다.

- priority_queue는 default로는 최소값이 root에 있기 때문에 이것을 그대로 사용해주면 된다.

 

- C++ 백준 11279번 STL Priority_queue 사용한 소스코드:

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    vector<int> result;
    int n, x;
    cin >> n;
 
    priority_queue<int> q;
    for (int i = 0; i < n; i++){
        cin >> x;
        if(x!=0){
            q.push(x);
        }else{
            if(q.empty()){
                result.push_back(0);
            }else{
                result.push_back(q.top());
                q.pop();
            }
        }
    }
    for (int i = 0; i < result.size(); i++){
        cout << result[i] << '\n';
    }
        return 0;
}

- 배열로 Heap 구현한 소스코드:

#include<stdio.h>
#define MAX 100001
 
typedef struct _Heap 
{
	int numOfData;
	int arr[MAX];
} Heap;
 
void initHeap(Heap* heap);
void Insert(Heap* heap, int data);
int Delete(Heap* heap);
 
int main() 
{
	int n, x, i;
	Heap heap;
	initHeap(&heap);
	scanf("%d", &n);
	for (i = 0; i < n; i++) 
    {
		scanf("%d", &x);
		if (x == 0) 
        {
			if (!heap.numOfData)
				printf("0\n");
			else
				printf("%d\n", Delete(&heap));
		}
		else 
			Insert(&heap, x);
	}
 
	return 0;
}

void initHeap(Heap* heap) 
{
	heap->numOfData = 0;
}
 
void Insert(Heap* heap, int data) 
{
	int idx = heap->numOfData + 1;
	while (idx != 1) 
    {
		if (data > heap->arr[idx / 2]) 
        {
			heap->arr[idx] = heap->arr[idx / 2];
			idx /= 2;
		}
		else
			break;
	}
	heap->arr[idx] = data;
	heap->numOfData++;
}
 
int Delete(Heap* heap) 
{
	int root = heap->arr[1];
	int last = heap->arr[heap->numOfData];
	heap->numOfData--;
 
	int pIdx = 1, Lchild = pIdx * 2, Rchild = pIdx * 2 + 1;
	int cIdx;
	while (Lchild <= heap->numOfData) 
    {
		if (Lchild == heap->numOfData) 
        {
			if (last < heap->arr[Lchild]) 
            {
				cIdx = Lchild;
				heap->arr[pIdx] = heap->arr[cIdx];
				pIdx = cIdx;
			}
			break;
		}
		else 
        {
			cIdx = heap->arr[Lchild] > heap->arr[Rchild] ? Lchild : Rchild;
			if (last > heap->arr[cIdx])
				break;
			else
				heap->arr[pIdx] = heap->arr[cIdx];
		}
		pIdx = cIdx;
		Lchild = pIdx * 2;
		Rchild = pIdx * 2 + 1;
	}
	heap->arr[pIdx] = last;
	return root;
}