[알고리즘] 우선순위 큐

우선순위 큐의 특징

• 우선순위 큐는 일반적인 큐와 다르게 우선순위가 높은 요소를 먼저 처리하는 자료구조
• 파이썬에서는 heapq 모듈을 사용하여 힙(Heap) 기반으로 구현

🔹 주요 특징

1. 우선순위 기반 처리
   • 낮은 숫자가 높은 우선순위(기본 heapq는 최소 힙)
   • 최대 힙을 구현하려면 값을 음수(-)로 변환하여 저장
2. 효율적인 삽입/삭제 연산
   • 삽입(push) → O(logN)
   • 삭제(pop) → O(logN)
   • 최솟값(또는 최댓값) 조회 → O(1)
3. 정렬보다 효율적
   • 전체 정렬이 필요할 때 O(N logN)이지만, 우선순위 큐는 필요한 요소만 정렬해서 빠르다.

 

 

heapq

파이썬에서 우선순위 큐(Priority Queue)를 구현할 때 가장 많이 사용하는 모듈은 heapq이다.
heapq는 최소 힙(Min Heap)을 기반으로 동작하며 우선순위가 낮은 값이 가장 먼저 나오는 구조이다.

해당 내용은 : https://wishlee0204.tistory.com/271

 

우선순위 큐를 사용하는 코딩 테스트 유형

우선순위 큐는 가장 작은(혹은 큰) 값을 빠르게 꺼내야 하는 문제에서 유용하다.

1. 최단 경로 문제 (다익스트라 알고리즘)

📌 예시 문제: "한 도시에서 다른 도시까지의 최단 경로 찾기"
📌 이유:

• 다익스트라 알고리즘은 현재 최단 거리인 노드를 먼저 처리해야 한다.
• 우선순위 큐를 사용하면 가장 짧은 거리의 노드를 빠르게 꺼낼 수 있다.

import heapq

def dijkstra(graph, start):
    INF = float('inf')
    distance = {node: INF for node in graph}
    distance[start] = 0
    pq = [(0, start)]  # (거리, 노드)

    while pq:
        dist, node = heapq.heappop(pq)
        if distance[node] < dist:
            continue
        for adj, weight in graph[node]:
            cost = dist + weight
            if cost < distance[adj]:
                distance[adj] = cost
                heapq.heappush(pq, (cost, adj))
    
    return distance

---

🚀 2. K번째 최소/최대값 찾기

📌 예시 문제: "배열에서 K번째로 작은 수 찾기"
📌 이유:

• 완전 정렬(O(N logN))보다 우선순위 큐로 K개만 유지하면 O(N logK)로 더 빠름.

import heapq

def kth_smallest(arr, k):
    return heapq.nsmallest(k, arr)[-1]

nums = [7, 10, 4, 3, 20, 15]
print(kth_smallest(nums, 3))  # 출력: 7

✅ 변형:

• heapq.nlargest(k, arr)[-1] → K번째로 큰 값
• heapq.heappushpop(heap, value) → 힙 크기 유지하며 최적화

---

🚀 3. 정렬된 여러 리스트 병합 (우선순위 큐 기반 정렬)

📌 예시 문제: "정렬된 K개의 리스트를 하나로 합치기"
📌 이유:

• 각 리스트에서 가장 작은 값을 우선순위 큐에 넣고, 빠르게 병합 가능.

import heapq

def merge_sorted_lists(lists):
    pq = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(pq, (lst[0], i, 0))  # (값, 리스트 인덱스, 원소 인덱스)

    result = []
    while pq:
        val, list_idx, elem_idx = heapq.heappop(pq)
        result.append(val)
        if elem_idx + 1 < len(lists[list_idx]):
            heapq.heappush(pq, (lists[list_idx][elem_idx + 1], list_idx, elem_idx + 1))
    
    return result

lists = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
print(merge_sorted_lists(lists))  
# 출력: [1, 2, 3, 4, 5, 6, 7, 8, 9]

✅ 시간 복잡도: O(N logK) (N=전체 원소 개수, K=리스트 개수)

---

🚀 4. 우선순위가 다른 작업 처리 (작업 스케줄링, CPU 스케줄링)

📌 예시 문제: "각 작업의 우선순위가 다를 때, 높은 우선순위부터 처리"
📌 이유:

• 우선순위 큐를 사용하면 우선순위가 높은 작업을 빠르게 선택 가능.

import heapq

tasks = [(3, "Low Priority"), (1, "High Priority"), (2, "Medium Priority")]
heapq.heapify(tasks)  # 최소 힙 구성

while tasks:
    priority, task = heapq.heappop(tasks)
    print(task)

# 출력:
# High Priority
# Medium Priority
# Low Priority

✅ 최대 힙 필요하면 (-우선순위, 작업) 형태로 변환

---

🚀 5. 그리디 알고리즘에서 최적 선택 (회의실 배정, 배낭 문제)

📌 예시 문제: "가능한 한 많은 회의를 배정하는 문제"
📌 이유:

• 빨리 끝나는 회의부터 선택해야 더 많은 회의를 배정할 수 있음.
• 종료 시간을 우선순위 큐에 넣고 빠르게 선택.

import heapq

meetings = [(1, 4), (2, 3), (3, 5), (5, 6)]
heapq.heapify(meetings)

count, last_end = 0, 0
while meetings:
    start, end = heapq.heappop(meetings)
    if start >= last_end:
        count += 1
        last_end = end

print(count)  # 최대 회의 개수

✅ 그리디(탐욕법) 문제에서 자주 사용