[Python] 우선순위큐 사용하기 - heapque, headq

1. heapq import

해당 포스팅에서는 우선순위큐를 사용하기 위해서 heapq 라이브러리를 활용한다.

import heapq

2. 우선순위큐 사용하기

우선순위큐에서는 낮은 숫자일수록 높은 우선순위를 가진다.

구현 내용은 아래와 같다.

# 사용할 리스트 선언 (que와는 달리 리스트를 활용한다)
heap_que = [1,5,9]
print(heap_que) #=> [1, 5, 9]

# 리스트와 넣을 item을 매개변수로 넘겨서 삽입한다
# 순서 자체는 정렬되지 않는다
heapq.heappush(heap_que,7)
print(heap_que) #=> [1, 5, 9, 7]

# 가장 우선순위인 item을 pop한다 (낮은 숫자가 우선순위가 높다)
print(heapq.heappop(heap_que)) #=> 1
print(heap_que) #=> [5, 7, 9]

# 새로운 item을 push 후에 가장 우선순위가 높은 item을 pop한다
heap_que = [5, 7, 9] 
print(heapq.heappushpop(heap_que,2)) #=> 2
print(heap_que) #=> [5, 7, 9]

# 가장 우선순위가 높은 item을 pop한 후에 새로운 item을 push 한다
heap_que = [5, 7, 9]
print(heapq.heapreplace(heap_que,2)) #=> 5
print(heap_que) #=> [2, 7, 9]

 

실제로 우선순위큐를 사용하게되면 단순히 숫자가 아니라 어떠한 값을 넣고 우선순위를 부여하게 된다.

이는 ( {우선순위} , {값} )으로 item을 구성할 수 있으며 아래와 같다.

heap_que = [(1,'T'),(5,'B'),(9,'C')]
print(heap_que) #=> [(1, 'T'), (5, 'B'), (9, 'C')]

heapq.heappush(heap_que,(7,'A'))
print(heap_que) #=> [(1, 'T'), (5, 'B'), (9, 'C'), (7, 'A')]

print(heapq.heappop(heap_que)) #=> (1, 'T')
print(heap_que) #=> [(5, 'B'), (7, 'A'), (9, 'C')]

heap_que = [(5,'B'),(7,'H'),(9,'C')]
print(heapq.heappushpop(heap_que,(2,'E'))) #=> (2, 'E')
print(heap_que) #=> [(5, 'B'), (7, 'H'), (9, 'C')]

heap_que = [(5,'B'),(7,'H'),(9,'C')]
print(heapq.heapreplace(heap_que,(2,'E'))) #=> (5, 'B')
print(heap_que) #=> [(2, 'E'), (7, 'H'), (9, 'C')]