5월5일 - [Python] PriorityQueue(우선순위 큐), heapq

PriorityQueue

사용법

from queue import PriorityQueue

pqueue = PriorityQueue()
pqueue.put((5, 'Python'))
pqueue.put((15, 'Javascript'))
pqueue.put((10, 'Java'))

arr = []
while not pqueue.empty():
  value, data = pqueue.get()
  arr.append((value, data))

print(arr)
# [(5, 'Python'), (10, 'Java'), (15, 'Javascript')]

 

선언

from queue import PriorityQueue
pqueue = PriorityQueue()

 

데이터 삽입

pqueue.put((1, 'Python'))  # 우선순위값(숫자), 데이터)

우선순위가 높을수록 우선순위 값이 낮아야 한다.

 

데이터 추출

우선순위, 데이터 = pqueue.get()

제일 앞에 위치한 (제일 우선순위가 높은) 데이터가 추출된다.

 

우선순위가 같은 경우

from queue import PriorityQueue

pqueue = PriorityQueue()
pqueue.put((2, 1))
pqueue.put((2, -1))
pqueue.put((2, 0))

print(pqueue.get())  # (2 -1)
print(pqueue.get())  # (2 0)
print(pqueue.get())  # (2 1)

우선순위 큐는 제일 첫번째 값에 대해서만 우선순위를 결정하는게 아닌

n번째 값들에 대해 1부터 n까지 작을 값을 기준으로 오름차순으로 정렬한다. 

즉, 1번째 값이 같을 경우 2번째 값들이 작은 값부터 오름차순으로 정렬되게 된다.

 

우선순위를 반대로

from queue import PriorityQueue

pqueue = PriorityQueue()
pqueue.put((-5, 'Python'))
pqueue.put((-15, 'Javascript'))
pqueue.put((-10, 'Java'))

arr = []
while not pqueue.empty():
  value, data = pqueue.get()
  arr.append((value, data))

print(arr)
# [(-15, 'Javascript'), (-10, 'Java'), (-5, 'Python')]

 

heapq

https://slowsure.tistory.com/130

[Python/파이썬] PriorityQueue & heapq / 우선순위큐와 힙큐

공부하다가 놀라운 반전을 발견했는데 

위 포스팅에 따르면 파이썬에서 PriorityQueue는 heapq 그 자체를 사용하는 라이브러리였다.

 

단지, Thread-safe 하게 사용하기 위해 확인 과정을 거치는게 다른 점인데 

이 때문에 특정 알고리즘 문제에서 PriorityQueue를 사용했을 때보다
heapq를 사용했을 때가 훨씬 시간이 적게 걸리는 걸 알 수 있었다.

 

문제

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

11286번: 절댓값 힙

 

PriorityQueue를 사용한 코드

from queue import PriorityQueue
pqueue = PriorityQueue()
import sys
input = sys.stdin.readline

for _ in range(int(input())):
  x = int(input())  
  if x != 0:
    pqueue.put((abs(x), x))
  else:
    if pqueue.empty():
      print(0)
    else:
      print(pqueue.get()[1])

 

heapq를 사용한 코드

import sys
input = sys.stdin.readline
import heapq
arr = []

for _ in range(int(input())):
  x = int(input())  
  if x != 0:
    heapq.heappush(arr, (abs(x), x))
  else:
    if len(arr) == 0:
      print(0)
    else:
      print(heapq.heappop(arr)[1])