[CS기초] 우선순위 큐(Priority Queue)

우선순위 큐

우선순위 큐(Priority Queue)는 pop 연산에서 가장 먼저 들어온 원소 대신 우선순위가 가장 높은 원소가 내보내지는 큐이다. 이는 일반적으로 힙(Heap)을 이용하여 구현됩니다.

우선순위 큐(최소 힙)를 나타낸 그림

 

힙(Heap)

우선순위 큐를 효율적으로 구현하기 위해 사용되는 특수한 이진 트리 형태의 자료구조. 힙은 다음 두 가지 조건 중 하나를 만족해야 한다.

• 최소 힙(Min-Heap) : 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같아야 한다. 즉, 루트 노드가 트리 전체에서 가장 작아야 한다.
• 최대 힙(Max-Heap) : 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같아야 한다. 즉, 루트 노드가 트리 전체에서 가장 커야 한다.

 

힙의 특징

• 완전 이진 트리 구조 : 트리의 모든 계층이 꽉 차 있고, 마지막 계층만 왼쪽부터 채워져 있는 형태를 가지고 있다.
• 우선순위 정렬 : 삽입/삭제 연산을 수행할 때 부모-자식 관계를 재배치해 항상 루트 노드에 최솟값/최댓값이 있도록 유지한다.
• 시간 복잡도 : 삽입/삭제가 계층을 이동하면서 일어나므로 O(logN)이라는 매우 효율적인 시간 복잡도를 가진다.

 

힙의 연산

삽입 연산

• 새로운 요소를 마지막 노드 다음(힙 가장 아래 계층의 맨 오른쪽)에 추가
• 부모 노드와 비교하며 힙 조건을 만족할 때까지 위로 이동(heapify-up)
• 최악의 경우 가장 위쪽 계층까지 logN번 이동하므로, 최대 시간 복잡도 O(logN)

삭제 연산

루트 노드(최댓값 또는 최솟값)를 제거

마지막 노드를 루트 노드로 옮기고, 자식 노드와 비교하며 힙 조건을 만족할 때까지 아래로 이동(heapify-down)

최악의 경우 가장 아래쪽 계층까지 logN번 이동하므로, 최대 시간 복잡도 O(logN)

 

파이썬에서 우선순위 큐의 구현

파이썬에서는 표준 라이브러리의 heapq 모듈을 통해 우선순위 큐를 구현한다. 다만, 기본적으로 최소 힙 구현만 지원하기 때문에 최대 힙을 구현하기 위해서는 음수 처리를 활용해야 한다.

최소 힙 구현

import heapq

# 힙 생성
heap = []

# 요소 삽입
heapq.heappush(heap, 10)  # 삽입
heapq.heappush(heap, 5)
heapq.heappush(heap, 7)

# 최솟값 제거
print(heapq.heappop(heap))  # 5
print(heapq.heappop(heap))  # 7

최대 힙 구현

import heapq

# 힙 생성
heap = []

# 요소 삽입 (값을 음수로 저장)
heapq.heappush(heap, -10)
heapq.heappush(heap, -5)
heapq.heappush(heap, -7)

# 최대값 제거 (음수 상태의 값을 다시 양수로 변환)
print(-heapq.heappop(heap))  # 10
print(-heapq.heappop(heap))  # 7