28. 우선순위 큐 (Priority Queue)

핵심 인사이트 (3줄 요약)

본질: 우선순위 큐(Priority Queue)는 삽입된 순서가 아닌 우선순위(Priority) 기준으로 원소를 꺼내는 추상 자료형(ADT)이다. 최솟값 또는 최댓값이 항상 먼저 나온다.

가치: 일반 큐(FIFO)로는 "긴급한 일부터 처리"하는 패턴을 구현할 수 없다. 최솟값/최댓값 추출 O(log n)을 보장하는 이진 힙(Binary Heap)으로 구현하며, 다익스트라 최단 경로, OS 작업 스케줄링, 이벤트 시뮬레이션에 필수적이다.

판단 포인트: 이진 힙 vs. 피보나치 힙(Fibonacci Heap) — 다익스트라 알고리즘에서 이진 힙은 O((V+E)log V), 피보나치 힙은 O(V log V + E)다. 이론적으로 피보나치 힙이 우수하지만 구현 복잡도로 인해 실무에선 이진 힙이 표준이다.

Ⅰ. 개요 및 필요성

┌──────────────────────────────────────────────────────┐
│           이진 최솟값 힙 (Min Binary Heap)            │
├──────────────────────────────────────────────────────┤
│                       1                              │
│                      / \                             │
│                     3   2                            │
│                    / \ / \                           │
│                   6  5 4  7                          │
│                                                       │
│ 최솟값(루트)은 항상 1 → 빠른 추출 O(log n)           │
│ 삽입(sift-up) + 삭제(sift-down): 모두 O(log n)       │
└──────────────────────────────────────────────────────┘

📢 섹션 요약 비유: 우선순위 큐는 응급실 접수 시스템이다. 일반 줄(FIFO)과 달리, 가장 위급한 환자(최솟값)가 먼저 진료를 받고, 새 환자가 오면 위급도에 따라 적절한 자리에 배치된다.

Ⅱ. 아키텍처 및 핵심 원리

주요 연산 복잡도

연산	이진 힙	피보나치 힙	비고
삽입	O(log n)	O(1) 분할 상환
최솟값 추출	O(log n)	O(log n)
키 감소	O(log n)	O(1) 분할 상환	다익스트라 최적화
삭제	O(log n)	O(log n)

배열 기반 힙 구현

배열 인덱스: 1-based
  부모(i) = i // 2
  왼쪽 자식(i) = 2*i
  오른쪽 자식(i) = 2*i + 1

삽입: 배열 끝에 추가 → sift-up (부모와 비교·교환)
추출: 루트 제거 → 끝 원소를 루트로 → sift-down

📢 섹션 요약 비유: 이진 힙 배열 표현은 완전 이진 트리를 배열에 눕혀놓은 것이다. 부모·자식 관계를 인덱스 계산으로 표현해서 포인터 없이도 트리 구조를 구현할 수 있다.

Ⅲ. 비교 및 연결

비교	일반 큐	우선순위 큐	정렬된 배열
삽입	O(1)	O(log n)	O(n)
최솟값 추출	O(n)	O(log n)	O(1)
구현 복잡도	매우 낮음	중간	낮음

📢 섹션 요약 비유: 우선순위 큐는 스마트 대기열이다. 일반 줄(큐)은 먼저 온 사람이 먼저 나가지만, 스마트 대기열은 가장 중요한 사람이 항상 먼저 나간다. 새 사람이 오면 중요도에 따라 자동으로 자리를 정한다.

Ⅳ. 실무 적용 및 기술사 판단

핵심 알고리즘 응용

다익스트라 최단 경로    → Min Priority Queue (최소 거리 노드 추출)
허프만 코딩            → Min Priority Queue (최소 빈도 심볼 병합)
A* 탐색               → f(n) = g(n)+h(n) 기반 Priority Queue
OS 프로세스 스케줄링   → Priority Queue (우선순위 기반 CPU 할당)
이벤트 시뮬레이션      → 타임스탬프 기반 Priority Queue

언어별 구현

import heapq
pq = []
heapq.heappush(pq, (2, 'task_b'))   # (우선순위, 데이터)
heapq.heappush(pq, (1, 'task_a'))
print(heapq.heappop(pq))  # (1, 'task_a') — 최솟값 우선

📢 섹션 요약 비유: 다익스트라 + 우선순위 큐는 GPS 내비게이션이다. 아직 방문하지 않은 도로 중 현재까지 가장 가까운 교차점(최솟값)을 선택해서 최단 경로를 찾는다.

Ⅴ. 기대효과 및 결론

기대효과	내용
효율적 최솟값 접근	O(log n) 삽입·추출
알고리즘 최적화	다익스트라, 허프만 등 핵심 알고리즘의 기반
스케줄링	OS·네트워크 우선순위 작업 처리

우선순위 큐는 컴퓨터 과학의 핵심 자료구조 중 하나다. Python heapq, Java PriorityQueue, C++ std::priority_queue로 표준 라이브러리에 내장되어 있으며, 그래프 알고리즘과 시스템 스케줄링에서 빠질 수 없는 도구다.

📢 섹션 요약 비유: 우선순위 큐는 병원 응급실 트리아지(Triage) 시스템이다. 환자가 오는 순서(일반 큐)가 아닌, 상태의 위급함(우선순위)에 따라 진료 순서를 결정해서 최적의 자원 배분을 실현한다.

📌 관련 개념 맵

개념	연결 포인트
이진 힙	우선순위 큐의 표준 구현
다익스트라	우선순위 큐 기반 최단 경로
힙 정렬	힙을 이용한 O(n log n) 정렬
피보나치 힙	키 감소 O(1) 지원 고급 힙
A 알고리즘*	휴리스틱 + 우선순위 큐

📈 관련 키워드 및 발전 흐름도

[이진 힙 — 배열 기반 Min/Max Heap]
    │
    ▼
[우선순위 큐 ADT — 추상 자료형으로 일반화]
    │
    ▼
[다익스트라·허프만 — 우선순위 큐 응용 알고리즘]
    │
    ▼
[피보나치 힙 — 이론적 최적 복잡도]
    │
    ▼
[분산 우선순위 큐 — 분산 시스템의 작업 스케줄링]

👶 어린이를 위한 3줄 비유 설명

우선순위 큐는 응급실 대기 시스템이에요! 먼저 온 순서가 아니라 가장 아픈 환자가 먼저 진료를 받아요.
이진 힙이라는 구조로 구현해서, 가장 급한 것을 꺼내거나 새로운 것을 넣을 때 모두 O(log n)이면 돼요!
내비게이션 최단 경로 탐색, 파일 압축, 운영체제 프로세스 스케줄링 등 어디서나 사용된답니다!