우선순위 큐의 개념

우선순위 큐(Priority Queue)는 큐(Queue)의 일종으로, 데이터를 일반적인 큐와는 달리 우선순위(Priority)에 따라 처리하는 자료구조입니다. 이를 통해 우선순위가 높은 데이터가 먼저 처리되는 것을 보장할 수 있습니다.

큐(Queue): "선입선출"(First In First Out, FIFO)의 원칙을 따르며, 먼저 삽입된 데이터가 먼저 삭제되어 처리되는 자료구조

구현 방법

우선순위 큐를 구현하는 대표적인 방법은 힙(Heap)을 이용한 구현입니다.

힙(Heap): 완전 이진 트리(Complete Binary Tree)의 일종으로, 부모 노드와 자식 노드 간의 대소 관계를 유지하는 자료구조

힙을 이용하여 우선순위 큐를 구현합니다. 이때, 최소 힙(Min Heap) 또는 최대 힙(Max Heap)을 사용할 수 있습니다.

최소 힙

우선순위가 가장 높은 데이터가 가장 작은 값이 되도록 구성합니다.
즉, 루트노드가 가장 작은 값을 가지며, 항상 부모노드는 자식노드보다 작은 값을 가집니다.

최대 힙

우선순위가 가장 높은 데이터가 가장 큰 값이 되도록 구성합니다.
즉, 루트노드가 가장 큰 값을 가지며, 항상 부모노드는 자식노드보다 큰 값을 가집니다.

Python

파이썬에서는 heapq 모듈을 제공하여 간단하게 우선순위 큐를 구현할 수 있습니다.

리스트를 최소 힙으로 변환하기

import heapq

nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
# heapify() 함수를 이용하여 리스트를 최소 힙으로 변환합니다.
heapq.heapify(nums)
print(nums)
# [1, 1, 2, 3, 3, 9, 4, 6, 5, 5, 5]

리스트를 최개 힙으로 변환하기

import heapq

nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

# 각 요소를 음수로 바꾸어 최대 힙으로 만들어줍니다.
max_heap = [-num for num in nums]
heapq.heapify(max_heap)

# 힙에서 요소를 꺼내면서 다시 양수로 바꿔줍니다.
max_vals = []
for _ in range(len(nums)):
    max_val = heapq.heappop(max_heap)
    max_vals.append(-max_val)

print(max_vals)
# [9, 6, 5, 5, 5, 4, 3, 3, 2, 1, 1]

heapq 모듈은 기본적으로 최소 힙(min heap)만 다룰 수 있습니다. 따라서 heappush, heappop, heapify 등의 함수를 사용하면 리스트가 최소 힙으로 유지되도록 동작합니다.

시간 복잡도

삽입과 삭제 모두 $O(log\ n)$의 시간 복잡도를 가집니다.

활용

우선순위 큐는 힙의 크기에 관계없이, 각 연산은 $O(log\ n)$의 시간 복잡도를 가지므로 대용량 데이터에 대해서도 빠른 속도로 동작합니다.
우선순위가 높은 작업을 먼저 처리해야 하는 시스템에서 매우 유용합니다. 예를 들어, 운영체제에서는 CPU 스케줄링, 네트워크에서는 패킷 처리, 알고리즘에서는 다익스트라 알고리즘 등에서 우선순위 큐가 활용됩니다.