우선순위 큐는 데이터를 추가한 순서와 상관없이, 데이터를 꺼내는 순서를 오름차순으로 하는 특징이 있다.
즉, 내부의 데이터를 항상 정렬된 상태로 보관하는 로직이 있으며, heapq 모듈을 통해 구현 가능하다.
put(), get() 메서드 모두 O(log n)의 시간복잡도를 가진다.
1️⃣ 클래스 임포트 및 선언
PriorityQueue 클래스는 queue 내장 모듈에서 제공한다.
from queue import PriorityQueue
queue = PriorityQueue()
만약 사이즈 제한을 두고 싶다면 선언 시, 속성으로 maxsize=?을 넣어준다.
2️⃣ 원소 추가와 제거(반환)
queue.put(x)로 추가, queue.get()으로 제거(반환)할 수 있다.
오름차순의 순서로 반환된다.
만약 역순으로 반환하고 싶다면 (-x, x)의 튜플 형식으로 삽입하면 된다.
3️⃣ 기타 메서드
from Queue import PriorityQueue
import sys
input = sys.stdin.readline
N = int(input())
queue = PriorityQueue()
for n in range(N):
command = int(input())
if command == 0:
if queue.empty():
print(0)
else:
x = queue.get()
print(x[1])
else:
queue.put((-command, command))
from Queue import PriorityQueue
import sys
input = sys.stdin.readline
N = int(input())
queue = PriorityQueue()
for n in range(N):
comm = int(input())
if comm == 0:
if queue.empty():
print(0)
else:
print(queue.get())
else:
queue.put(comm)
from Queue import PriorityQueue
import sys
input = sys.stdin.readline
N = int(input())
queue = PriorityQueue()
for n in range(N):
comm = int(input())
if comm == 0:
if queue.empty():
print(0)
else:
x = queue.get()
print(x[1])
else:
if comm < 0:
queue.put((-comm, comm))
else:
queue.put((comm, comm))