우선순위 큐

PKH·2025년 4월 26일

우선순위 큐란?

우선순위 큐는 일반 큐에서 선입선출로 pop이 되는 과정과는 다르게 우선순위가 가장 높은 원소가 나오는 큐이다.
큐에 들어가는 각 원소는 우선순위를 가지고 있으며, 이 우선순위를 기준으로 pop 연산이 수행된다.
우선순위 큐의 특징은 다음과 같다.

원소의 추가가 O(lgN)

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

우선순위가 가장 높은 원소 제거 O(lgN)

우선순위 큐의 연산이 빠른 이유는 바로 힙의 구조를 사용하기 때문이다.

큐(Queue) : 선입선출(FIFO)

우선순위 큐(Priority Queue) : 우선순위가 높은 데이터가 먼저 나가는 구조

힙(Heap) : 루트 노드에 최댓값 or 최솟값을 저장하고 있는 완전이진트리

최소 힙의 예시

삽입(Inset)

값을 힙에 삽입할 때는 항상 말단 노드로 추가한 뒤 부모 노드와 값을 비교해 가며 위치를 조정한다. 부모보다 값이 작다면 서로 자리를 바꾸는 방식으로 최소 힙에서는 값이 위로 올라가는 구조다.

35를 먼저 넣으면 트리의 루트가 됨

55는 35보다 크므로 자식으로 들어감

15는 부모인 35보다 작으므로 위치를 교체한다.
이러한 과정을 반복하며 새로운 노드가 추가되면 부모와 비교하며 값이 부모보다 작아질 때까지 자리를 교환하기 때문에 O(lgN)의 시간이 걸린다.

제거(Erase)

힙에서 가장 우선순위가 높은 원소(루트)를 제거할 때는 트리의 마지막 노드를 루트에 올린 뒤 자식 노드들과 비교하여 다시 위치를 조정한다.

8을 삭제하고 가장 마지막에 추가된 52를 루트에 배치

52보다 자식인 12와 13중 더 작은 12와 교환

이후 16, 22와도 반복적으로 위치를 조정하며 내려감

이렇게 heap의 구조를 이용하여 우선순위 큐를 구현할 수 있다.

코드

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

int heap[100002];
int sz = 0;

void push(int x)
{
	heap[++sz] = x;
	int idx = sz;
	while(idx > 1)
	{
		if(heap[idx] >= heap[idx/2]) break;
		swap(heap[idx], heap[idx/2]);
		idx /= 2;
	}
}

int top()
{
	return heap[1];
}

void pop()
{
	heap[1] = heap[sz--];
	
	int idx = 1;
	while(2*idx <= sz)
	{
		int l = idx *2, r = idx * 2 + 1;
		int m = l;
		if(r <= sz && heap[m] > heap[r]) m = r;
		if(heap[idx] <= heap[m]) break;
		swap(heap[idx], heap[m]);
		idx = m;
	}
}

void test()
{
	push(10);
	push(2);
	push(3);
	cout << top() << '\n';
	push(5);
	pop();
	cout << top() << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	test();
	return 0;
}