[Algorithm] 백준 1927 - 최소 힙 in Python(파이썬)

💡 백준 1927:

최소 힙 기본 구조 활용

🌱 코드 in Python

알고리즘: Min Heap

min heap과 관련하여 파이썬에 PriorityQueue와 Heapq 모듈이 이미 구현되어 있다
Heapq의 경우 이진트리 형태로 구현이 되어있어 이 자체가 min-heap 구조를 가진다

Heapq를 몰라서 처음에는 PriorityQueue를 활용하여 문제를 풀어보았다

from queue import PriorityQueue
import sys

pq = PriorityQueue()
n = int(sys.stdin.readline())
for i in range(n):
	num = int(sys.stdin.readline())
	if num == 0:
		if pq.qsize() == 0:
			print(0)
		else:
			print(pq.get())
	else:
		pq.put(num)

그런데 이 모듈로 문제를 제출하고 나니, 다른 파이썬 제출자에 비해 내 제출 코드의 속도가 많이 느리길래 찾아봤더니 대부분 Heapq로 문제를 풀고 있었다

import heapq, sys

heap = []
n = int(sys.stdin.readline())
for i in range(n):
	num = int(sys.stdin.readline())
	if num == 0:
		if len(heap) == 0:
			print(0)
		else:
			print(heapq.heappop(heap))
	else:
		heapq.heappush(heap, num)

heapq나 PriorityQueue나 작동방식은 똑같은 거 같은데 왜 이렇게 차이가 나나 찾아보니
https://slowsure.tistory.com/130
이 글에 잘 정리가 되어 있었다

요약하자면 PritorityQueue는 thread safe 유효성 체크 과정이 들어있어
heapq보다 더 시간이 오래 걸리는 것이었다

알고리즘 문제를 풀 때는 heapq만 써도 충분할 듯!
다음에 더 자세히 모듈에 대해서도 공부해 봐야겠다

🧠 기억하자

1. heapq
   • 리스트를 선언한 상태에서 heapq.heappush(list, num) || heapq.heappop(list)와 같이 사용할 수 있다

2. PriorityQueue
   • pq = PriorityQueue()와 같이 선언 후 사용
   • put, get 함수 사용
   • pq.qsize() 함수로 큐의 사이즈를 알 수 있다

백준 1927 바로가기