Blog
Series
Projects
블로그로 돌아가기
자료구조크래프톤 정글

[자료구조] 우선순위 큐

약 10분 소요
[자료구조] 우선순위 큐

우선순위 큐(Priority Queue)란?

우선순위 큐(Priority Queue)는 각 요소에 우선순위(priority)를 부여하여, 우선순위가 높은 요소를 가장 먼저 처리하는 추상 자료구조이다

일반적인 큐(Queue)가 선입선출(FIFO)로 작동하고

스택(Stack)이 후입선출(LIFO)로 작동하는 데 비해,

우선순위 큐는 우선순위 값에 따라 출력 순서가 결정된다.

우선순위가 높을수록 큐의 앞쪽에 위치하며, 두 요소의 우선순위가 같다면 보통 삽입된 순서대로 처리된다

⚠️ 주의: 우선순위 큐는 개념적으로 큐를 확장한 추상 자료형일 뿐, 특정 구현에 종속되지 않는다.

흔히 우선순위 큐를 힙(Heap)과 동일시하기도 하지만, 이는 스택을 배열/연결 리스트와 혼동하는 것과 같다.

우선순위 큐는 힙을 비롯한 다양한 방법으로 구현 가능하며, 힙은 그중 가장 효율적인 구현 방법일 뿐이다.

우선순위 큐의 주요 연산은 다음과 같다:

연산설명
push(x, p)우선순위 p를 가진 요소 x를 큐에 추가
pop()현재 큐에서 가장 높은 우선순위의 요소를 제거하고 반환. 비어 있으면 예외 발생
peek()큐에서 가장 높은 우선순위의 요소를 반환만 (제거하지 않음). 비어 있으면 예외 발생
is_empty()큐가 비어 있으면 True, 아니면 False

이러한 연산을 통해 우선순위가 가장 높은 요소를 빠르게 추출할 수 있다는 점이 우선순위 큐의 핵심이다.

힙(Heap)이란?

우선순위 큐를 효율적으로 구현하기 위해 가장 널리 쓰이는 자료구조가 힙(Heap)이다.

힙은 완전 이진 트리 형태로 요소를 저장하며,

부모 노드의 우선순위가 자식 노드들의 우선순위보다 항상 높거나 같은 특성을 지닌다 (최대 힙의 경우).

이 규칙을 만족함으로써 루트(root) 노드에는 항상 최우선순위 요소가 위치하게 된다.

💡완전 이진 트리란?

모든 레벨이 완전히 채워져 있고 마지막 레벨의 노드들도 가능한 한 왼쪽부터 채워진 이진 트리를 말한다.

이러한 완전 이진 트리 구조 덕분에 힙의 높이는 최소한으로 유지되며, 노드 개수가 N일 때 높이는 약 O(log N) 수준에 불과하다.

힙에는 최대 힙(Max Heap)과 최소 힙(Min Heap) 두 가지 종류가 있는데,

최대 힙은 부모 노드가 자식보다 크거나 같아서 가장 큰 값이 루트에 오는 구조이고,

최소 힙은 부모 노드가 자식보다 작거나 같아서 가장 작은 값이 루트에 오는 구조다.

우선순위 큐의 우선순위 정의에 따라 최대 힙이나 최소 힙을 선택해 사용할 수 있다.

힙의 주요 연산 원리

힙은 삽입과 삭제 연산 시 다음과 같은 방식을 통해 힙 특성을 유지한다.

  • 삽입: 새로운 요소를 힙의 마지막 위치(완전 이진 트리의 마지막 노드 자리)에 추가한 뒤, 부모 노드와 우선순위를 비교한다. 만약 새 요소의 우선순위가 부모보다 높으면(예: 최대 힙에서 값이 더 크다면) 부모와 자리를 바꾸고 한 단계 위로 올라간다. 이 과정을 루트에 도달하거나 더 이상 부모보다 우선순위가 높지 않을 때까지 반복하여 힙 특성을 복원한다.

  • 삭제: 최우선순위 요소(루트 노드)를 제거하면 힙이 빈 자리가 생기므로, 마지막 노드를 임시로 루트 위치로 가져온다. 이후 루트 노드의 우선순위를 두 자식과 비교하여 힙 특성이 만족될 때까지 아래로 내려보낸다. (예: 최대 힙에서는 루트 노드가 두 자식 중 더 큰 값과 교환하며 내려감) 이 과정을 더 이상 자식 노드보다 우선순위가 낮은 경우가 없을 때까지 반복하여 힙 특성을 복구한다.

최대 힙에서 최우선순위 요소 T를 삭제하는 과정. (1)

루트 T를 제거하고 마지막 노드 K를 루트로 이동. (2)

자식 노드 S, R보다 K의 우선순위가 낮아 힙 특성 위배 → 둘 중 더 우선순위 높은 S와 교환. (3)

계속 내려가며 K를 P와 교환해 힙 특성 복원. (빨간색 노드는 교환되는 요소들)

위 삽입/삭제 과정에서 보듯, 힙은 한 단계 내려가거나 올라갈 때마다 트리 높이의 1층을 이동하게 되므로 연산 복잡도는 트리 높이에 비례하게 된다. 완전 이진 트리 구조 상 높이가 O(log N) 이므로, 힙에 요소를 삽입하거나 삭제(pop)하는 연산은 O(log N)에 실행된다(andrew.cmu.edu). 반면, 최우선순위 요소를 확인(peek)하는 연산은 단순히 루트 값을 읽기만 하면 되므로 O(1)로 매우 빠르다.

😢 만약 배열이나 연결 리스트로 우선순위 큐를 구현하면… 매 삽입/삭제 때 정렬을 유지하거나 최댓값을 찾기 위해 O(n) 시간이 걸릴 수 있다.

😀 하지만 힙을 이용하면 삽입과 삭제를 모두 O(log n)으로 효율화할 수 있다. 우선순위 큐에 힙이 빈번히 사용되는 이유가 바로 이 효율성이다!


요약하면, 힙은 우선순위 큐에 특화된 트리 구조로서, 항상 루트에 최고 우선순위 데이터를 유지하고, 이를 제거/추가할 때도 로그arithmic 시간 내에 처리할 수 있게 해준다geeksforgeeks.org.

힙을 이용한 우선순위 큐 구현

우선순위 큐는 내부적으로 힙을 사용하여 구현되는 경우가 많다.

완전 이진 트리 형태인 힙은 배열로 손쉽게 저장 및 관리가 가능하고,

삽입/삭제 시 트리 재구성이 빠르기 때문이다

일반 큐와 비교하면, 우선순위 큐는 데이터의 출력 순서가 FIFO가 아닌 “우선순위 순”이라는 점만 다르다.

스택/큐와 마찬가지로 우선순위 큐도 추상 자료구조이므로,

실제 구현에서는 배열, 연결 리스트, 트리 등 다양한 방법을 사용할 수 있다.

예를 들어 정렬된 배열로 구현하면 push시에 정렬 비용이 발생하는 대신 pop은 즉시 수행되며,

정렬되지 않은 배열로 구현하면 push는 빠르지만 pop시에 최고 우선순위 탐색 비용이 발생한다

아래는 여러 구현 방법 별 연산 복잡도 비교이다.

구현 방식삽입삭제(pop)최고값 조회(peek)
정렬된 배열O(n)O(1)O(1)
정렬된 연결리스트O(n)O(1)O(1)
정렬되지 않은 배열O(1)O(n)O(n)
정렬되지 않은 연결리스트O(1)O(n)O(n)
이진 힙O(log n)O(log n)O(1)

이처럼 이진 힙(binary heap)을 사용하면 삽입과 삭제를

모두 O(log n)으로 줄일 수 있어, 가장 균형잡힌 효율을 제공한다.

실제로 다익스트라 최단경로, 허프만 코딩, 최소 신장 트리(Prim 알고리즘) 등 많은 알고리즘에서 우선순위 큐를 사용할 때 내부적으로 이진 힙을 활용한다.

파이썬 heapq 모듈 사용하기

파이썬에서는 기본 자료구조로 최소 힙(Min Heap)을 제공하며,

heapq 모듈을 통해 우선순위 큐를 사용할 수 있다.

heapq 모듈은 리스트를 마치 힙처럼 다룰 수 있는 함수들을 제공하며,

주요 연산으로 heapq.heappush(heap, item) (삽입)과 heapq.heappop(heap) (최소값 삭제 및 반환) 등이 있다.

다음은 파이썬에서 최소 힙을 사용하는 간단한 예시이다:

import heapq

numbers = [5, 1, 7, 3]
heap = []
for num in numbers:
    heapq.heappush(heap, num)      # 리스트를 힙처럼 사용하여 요소 추가

print([heapq.heappop(heap) for _ in range(len(heap))])
# 출력: [1, 3, 5, 7]  (오름차순 정렬된 결과: 최소 힙이므로 가장 작은 값부터 나온다)

기본적으로 heapq는 최소 힙이므로, 가장 작은 값이 먼저 나온다.

만약 최대 힙처럼 동작하도록 구현하고 싶다면 우선순위 값을 음수로 저장하는 트릭을 사용할 수 있다.

예를 들어 위 예시에서 큰 수가 먼저 나오게 하려면, heappush할 때 -num을 저장하고 heappop으로 뽑을 때 다시 부호를 되돌리면 된다.

heap = []
for num in numbers:
    heapq.heappush(heap, -num)     # 음수 값으로 저장 (최대 힙 효과)

print([-heapq.heappop(heap) for _ in range(len(heap))])
# 출력: [7, 5, 3, 1]  (내림차순 결과: 가장 큰 값부터 나온다)

💡 Tip: 튜플을 이용하면 우선순위와 실제 데이터를 함께 저장할 수 있다.

예를 들어 (priority, value) 형태로 heappush하면

튜플의 첫 번째 값인 priority를 기준으로 최소 힙 정렬이 된다.

이 방법을 이용해 (우선순위 값은 첫 번째 요소로, 실제 객체는 두 번째 요소로) 복잡한 데이터의 우선순위 큐도 구현할 수 있다.

(단, 우선순위 값이 같을 때는 튜플의 두 번째 값까지 비교하게 되므로, 데이터 객체끼리 비교가 불가능한 타입이면 오류가 발생할 수 있음)

파이썬의 heapq 모듈은 리스트를 힙으로 다룰 수 있게 해줄 뿐만 아니라,

heapq.heapify(list) 함수를 통해 기존 리스트를 한번에 힙 구조로 변환하거나

heapq.nlargest, heapq.nsmallest 등 편의 기능도 제공한다.

다만 이러한 함수들도 기본적으로 최소 힙 특성을 따른다는 점에 유의해야 한다.

(예를 들어 nlargest는 내부적으로 최소 힙을 활용하여 가장 큰 값을 뽑아낸다).

우선순위 큐의 활용 예시

우선순위 큐(힙)는 다양한 알고리즘 및 시스템 구현에서 활용된다.

특히 정렬이나 탐색에서 효율성을 높이거나, 실시간 시스템에서 우선순위에 따른 작업 스케줄링을 구현하는 데 필수적이다.

대표적인 세 가지 활용 예시를 살펴보자.

1. 다익스트라 최단 경로 알고리즘

그래프에서 한 정점부터 다른 정점들까지의 최단 경로를 구하는 다익스트라(Dijkstra) 알고리즘은 우선순위 큐(최소 힙)를 사용하여 가장 짧은 거리를 가진 정점을 효율적으로 선택합니다. 일반적인 구현에서는 (현재까지의 거리, 정점) 형태의 정보를 우선순위 큐에 넣고, 현재 가장 가까운 정점을 계속해서 꺼내어 경로를 확장해 나갑니다. 이렇게 하면 우선순위 큐가 가장 작은 거리를 우선으로 탐색하게 되어 불필요한 경로 탐색을 줄일 수 있습니다.

import heapq

def dijkstra(graph, start):
    # 그래프: {정점: [(인접정점, 가중치), ...], ...}
    # start부터 각 정점까지의 최단거리를 계산하여 딕셔너리로 반환
    distances = {v: float('inf') for v in graph}
    distances[start] = 0
    pq = [(0, start)]  # (현재까지 거리, 정점)

    while pq:
        dist, vertex = heapq.heappop(pq)
        if dist > distances[vertex]:
            continue  # 이미 더 짧은 경로로 처리된 정점은 무시
        for neighbor, weight in graph[vertex]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))
    return distances

# 예시 그래프: 각 노드간 가중치 (무방향 그래프)
graph = {
    'A': [('B', 5), ('C', 1)],
    'B': [('A', 5), ('C', 2), ('D', 1)],
    'C': [('A', 1), ('B', 2), ('D', 4), ('E', 8)],
    'D': [('B', 1), ('C', 4), ('E', 3), ('F', 6)],
    'E': [('C', 8), ('D', 3)],
    'F': [('D', 6)]
}
print(dijkstra(graph, 'A')['F'])  # A에서 F까지의 최단거리 ->  (A->B->D->F 경로 등)

위 코드에서 우선순위 큐 pq는 항상 현재 남은 정점 중 가장 가까운 거리에 있는 정점을 제공하므로, 다익스트라 알고리즘을 효율적으로 (O(E log V) 시간에) 수행할 수 있습니다. 만약 우선순위 큐를 사용하지 않고 매 단계 최단 거리를 선형 탐색한다면 O(V^2) 시간이 걸릴 수 있는데, 우선순위 큐 덕분에 큰 그래프에서도 성능을 높일 수 있습니다.

2. K번째로 작은 수 찾기

정렬되지 않은 배열에서 K번째로 작은 원소를 찾는 문제도 우선순위 큐로 효율적으로 해결할 수 있다.

가장 직관적인 방법은 배열을 정렬해서 K번째 값을 찾는 것이지만(O(n log n) 시간),

우선순위 큐를 사용하면 완전 정렬 없이 필요한 값만 찾아낼 수 있다.

예를 들어, 배열에서 가장 작은 K개의 요소만 뽑아내면 K번째 작은 값까지를 구할 수 있을 것이다.

최소 힙을 이용하면 배열의 모든 값을 힙에 넣은 뒤 K번 pop()하여 해결할 수 있고,

최대 힙을 이용하면 크기가 K인 힙을 유지하면서 더 큰 값들은 버리는 방법으로도 구현할 수 있다.

(후자가 더욱 효율적인 방법으로 O(n log K) 시간 복잡도를 가짐).

간단한 예로, 다음은 파이썬 heapq로 가장 작은 3개 값을 추출하여 결과를 얻는 코드이다:

import heapq

data = [7, 1, 3, 4, 8, 2]
k = 3

heapq.heapify(data)  # 리스트를 바로 최소 힙으로 변환
smallest_k = [heapq.heappop(data) for _ in range(k)]
print(smallest_k)  # [1, 2, 3]

위 예시에서는 heapq.heapify로 리스트를 힙 구조로 만든 후

heappop을 3번 실행하여 [1, 2, 3]을 얻었다.

이처럼 우선순위 큐를 활용하면 전체 정렬을 하지 않고도 K개의 최소값만 추출하거나,

필요에 따라 최대값을 추출하는 등 부분적인 정렬 문제를 효과적으로 해결할 수 있다.

3. CPU 작업 스케줄링

운영체제의 CPU 스케줄링에서도 우선순위 큐 개념이 널리 활용됩니다. 여러 개의 작업(task)이 대기하고 있을 때, 우선순위가 높은 작업을 CPU에 먼저 할당하는 우선순위 스케줄링이 일반적으로 사용됩니다. 이때 작업들을 우선순위 큐에 넣어 관리하면 항상 현재 가장 우선순위 높은 작업을 빠르게 가져올 수 있습니다.

예를 들어, 간단한 작업 리스트가 다음과 같다고 가정합시다:

python
복사편집
import heapq

# (작업명, 우선순위) 형태의 작업 리스트 (숫자가 클수록 우선순위 높음)
tasks = [("작업1", 3), ("작업2", 1), ("작업3", 2)]

# 우선순위가 높은 순으로 처리하기 위해 최대 힙 사용 (우선순위를 음수로 저장)
pq = []
for task, priority in tasks:
    heapq.heappush(pq, (-priority, task))

# 우선순위 순서대로 작업을 처리하는 순서
order = [heapq.heappop(pq)[1] for _ in range(len(pq))]
print(order)  # ['작업1', '작업3', '작업2']

위 결과 ['작업1', '작업3', '작업2']는 우선순위 3 → 2 → 1 순으로 작업이 선택된 것을 보여줍니다. 실제 운영체제 스케줄러에서는 새로운 작업이 도착하거나 실행 중 작업의 우선순위가 변경될 수도 있지만, 우선순위 큐를 사용한 작업 대기열을 유지하면 이러한 동적 상황에서도 항상 우선순위가 가장 높은 작업을 효율적으로 선택할 수 있습니다. 이 방식은 라운드 로빈이나 FCFS(First-Come First-Served) 같은 방식과 달리 긴급한 작업을 지연 없이 처리할 수 있다는 장점 때문에, 현실 세계의 프로세스 스케줄링에서도 중요하게 쓰입니다.

결론

우선순위 큐는 요소의 우선순위에 따라 처리 순서를 결정함으로써, 프로그래밍에서 중요도가 높은 작업을 신속하게 처리할 수 있게 해주는 구조입니다. 내부 구현에 따라 성능 차이가 있지만, 힙을 이용한 우선순위 큐는 삽입/삭제를 로그 시간에 수행하며 매우 효율적이어서 다양한 알고리즘 (최단경로, 정렬, 코딩) 및 시스템 구현(스케줄러 등)에 필수적으로 활용됩니다.

스택과 큐 등을 이해했다면 우선순위 큐도 개념적으로 어렵지 않으며, 이를 통해 자료구조의 응용을 엿볼 수 있습니다. 더 나아가 힙을 이용한 정렬 알고리즘인 힙 정렬(Heap Sort)이나, 우선순위 큐의 특성을 극대화한 다양한 힙 구조(예: 이진 탐색 트리 기반 큐, 피보나치 힙 등)로도 확장이 가능합니다. 우선순위 큐를 확실히 이해해두면 이런 고급 자료구조나 알고리즘을 배울 때 큰 도움이 될 것입니다.