[Algorithm] 우선순위 큐 이론 + heapq 사용법

❗우선순위 큐(Priority Queue)란?

일반적인 큐와 같은 성질을 가지고 있지만 삽입될 때 우선순위를 가지고 이에 따라 값이 처리되는 논리적 자료구조이다.

 

 

❗구현 방법

우선순위 큐는 배열, 연결 리스트, 힙(Heap) 등으로 구현할 수 있지만, 힙을 사용하는 것이 가장 일반적이다.

힙은 최소힙과 최대힙으로 구분되며 최소 힙을 사용하면 우선순위가 낮은 값(최소값)이 루트에 위치하게 되어, O(log n)의 시간 복잡도로 우선순위가 가장 높은 요소를 추출할 수 있다.

반대로 최대힙은 최댓값이 루트에 위치하게 된다. 

 

 

❗파이썬의 heapq

파이썬에서는 heapq 라이브러리를 활용하여 우선순위 큐를 구현할 수 있다.

 

✏️import heapq

from heapq import heapify, heappush, heappop

표준 라이브러리인 heapq 모듈을 불러오는 부분이다.

 

✏️heapify

# 초기 리스트
heap = [5, 3, 8, 1, 6, 7]
# heap = [-x for x in heap]

# 리스트를 힙으로 변환
heapify(heap)

print(heap)
# [1, 3, 7, 5, 6, 8]

heapify는 기존에 존재하는 리스트를 heap으로 변경할 때 사용하는 함수이다. 파이썬의 heapq는 기본적으로 최소힙으로 만들어지기 때문에 최대힙으로 만들고 싶다면 리스트의 원소를 전부 마이너스로 변경 후 heapify 함수를 사용하면 최대힙을 만들 수 있다.

 

✏️heappush

# 힙에 원소 추가
heappush(heap, 4)

print(heap)
# [1, 3, 4, 5, 6, 8, 7]

힙을 유지하면서 원소를 넣고 싶으면 heappush를 사용해야 한다. 

 

✏️heappop

# 최솟값 제거
min_value = heappop(heap)
# max_value = -heappop(heap)

print(heap)
# [3, 5, 4, 7, 6, 8]

힙은 pop을 통해 루트에 위치한 값을 알아낼 수 있다. 최소힙의 경우엔 최솟값, 최대힙의 경우엔 최댓값을 반환한다.

최대힙에서 최댓값을 가져올 땐, 마이너스로 들어간 원소를 다시 원래 값으로 복구하기 위해 마이너스를 붙여준다.

 

✏️top

# 최솟값
top_value = heap[0]

# 최댓값
top_value = -heap[0]

pop을 하면 루트값을 같이 반환하지만 삭제는 하지 않고 루트 원소의 값을 알고 싶을 땐, heap의 0번째 인덱스에 접근할 수 있다. 마찬가지로 최댓값은 원래 값에 마이너스를 붙여준다.

 

 

❗참고문제

https://www.acmicpc.net/problem/1927

https://www.acmicpc.net/problem/11279