anonymous.rs

자료구조: 우선순위 큐 (Priority Queue)

7 min read

우선순위 큐, Priority Queue

소프트웨어 엔지니어링 인터뷰 및 실무에서 데이터 처리 순서를 제어할 때 핵심적으로 사용되는 **우선순위 큐(Priority Queue)**에 대해 알아보겠습니다.

1. 우선순위 큐란?

일반적인 큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 FIFO (First-In, First-Out) 구조입니다. 반면, 우선순위 큐는 들어온 순서와 상관없이 우선순위가 가장 높은 데이터가 먼저 나가는 자료구조입니다.

응급실을 생각해보면 이해가 쉽습니다. 먼저 도착한 환자보다 생명이 위급한 환자(우선순위가 높은 환자)를 먼저 치료하는 것과 같은 원리입니다.

2. 우선순위 큐의 주요 연산

  • 삽입 (Push/Enqueue): 우선순위를 가진 데이터를 큐에 추가합니다.
  • 추출 (Pop/Dequeue): 큐에 있는 데이터 중 우선순위가 가장 높은 데이터를 제거하고 반환합니다.
  • 조회 (Peek/Top): 우선순위가 가장 높은 데이터를 제거하지 않고 확인만 합니다.

3. 우선순위 큐의 구현 방법 비교

우선순위 큐는 배열, 연결 리스트, 힙(Heap) 등 다양한 방법으로 구현할 수 있습니다. 하지만 성능 차이 때문에 일반적으로 힙(Heap)을 이용하여 구현합니다.

구현 방법삽입 (Push) 시간 복잡도추출 (Pop) 시간 복잡도특징
정렬되지 않은 배열/연결 리스트삽입은 맨 끝에 하면 되지만, 추출 시 모든 원소를 탐색하여 최고 우선순위를 찾아야 함.
정렬된 배열/연결 리스트추출은 맨 앞(또는 끝)에서 바로 가져오면 되지만, 삽입 시 올바른 위치를 찾고 데이터를 이동시켜야 함.
힙 (Heap)완전 이진 트리 기반으로, 삽입과 추출 모두 균형 잡힌 우수한 성능을 보장함.

힙(Heap)은 우선순위 큐를 구현하기 위한 ‘가장 효율적인 밑바탕(자료구조)‘이고, 우선순위 큐는 힙을 이용해 구현된 ‘개념(추상 자료형, ADT)‘이라고 이해하시면 됩니다.

4. 파이썬에서의 우선순위 큐 사용

파이썬에서는 주로 heapq 모듈을 사용하여 우선순위 큐를 구현합니다. queue.PriorityQueue 클래스도 있지만 내부적으로 heapq를 사용하며 스레드 세이프(Thread-safe) 처리가 되어 있어 알고리즘 문제 풀이에서는 오버헤드가 적은 heapq를 선호합니다.

import heapq
 
pq = []
 
# 우선순위 큐에 데이터 삽입: (우선순위, 값) 형태의 튜플 사용
# 파이썬 heapq는 최소 힙이므로 첫 번째 요소가 작을수록 우선순위가 높음
heapq.heappush(pq, (2, "Task B"))
heapq.heappush(pq, (1, "Task A")) # 우선순위가 가장 높음 (숫자가 작음)
heapq.heappush(pq, (3, "Task C"))
 
# 우선순위 큐에서 데이터 추출
while pq:
    priority, task = heapq.heappop(pq)
    print(f"우선순위: {priority}, 작업: {task}")
 
# 출력 결과:
# 우선순위: 1, 작업: Task A
# 우선순위: 2, 작업: Task B
# 우선순위: 3, 작업: Task C

5. 우선순위 큐의 활용 사례

우선순위 큐는 컴퓨터 과학의 다양한 분야에서 널리 활용됩니다.

  1. 운영체제(OS)의 작업 스케줄링: 시스템 프로세스와 사용자 프로세스의 우선순위를 다르게 부여하여 CPU 시간을 할당합니다.
  2. 네트워크 트래픽 제어: 중요도가 높은 패킷(예: VoIP 음성 데이터)을 일반 데이터보다 먼저 전송합니다.
  3. 다익스트라(Dijkstra) 알고리즘: 그래프에서 최단 경로를 찾을 때, 현재까지 발견된 가장 가까운 정점을 먼저 방문하기 위해 우선순위 큐를 사용합니다.
  4. A (에이스타) 알고리즘:* 길 찾기 알고리즘에서 휴리스틱 추정치가 가장 낮은 노드를 우선적으로 탐색할 때 사용됩니다.
  5. 허프만 코딩 (Huffman Coding): 데이터 압축 알고리즘에서 등장 빈도가 낮은 문자들을 먼저 묶어 트리를 구성할 파이썬(Python)에서의 힙 사용.

요약

우선순위 큐는 데이터의 입력 순서가 아닌 ‘우선순위’에 따라 데이터를 처리해야 할 때 필수적인 자료구조입니다. 삽입과 삭제 연산에서 의 성능을 보장하는 힙(Heap) 자료구조를 통해 주로 구현되며, 각종 스케줄링 및 그래프 알고리즘의 핵심 요소로 활약합니다. 인터뷰에서 “가장 크거나 작은 순서대로 처리”, “우선순위에 따른 작업” 등의 상황이 주어진다면 우선순위 큐를 반드시 떠올리셔야 합니다.

 
# list 를 heapify
 
import heapq
 
min_heap = [5,3,9,4,1,2,6]
 
heapq.heapify(min_heap) # [1,3,2,4,5,9,6], O(N)
 
heapq.heappop(min_heap) # [1], O(logN)
# shift down 연산을 어떻게?
 
heapq.heappush(min_heap, 1) # [2,3,6,4,5,9,"1"], O(logN)
# Shift Up 연산을 어떻게
import heapq
 
max_heap = [5,3,9,4,1,2,6]
 
heapq._heapify_max(max_heap)
 
value = heapq._heappop_max(max_heap)

min heap 을 만드는 방식을 이용해서 max heap 구현

max_heap = [5,3,9,4,1,2,6]
max_heap = [i * -1 for i in max_heap]
heapq.heapify(max_heap)
weight = heapq.heappop(max_heap)
value = -1 * weight

Graph View