1927번 최소 힙

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

아이디어

heapq를 사용할 줄 알면 풀 수 있는 문제이다. 이 문제 덕분에 heapq를 확실히 알게 되었다.

heapq에서 주로 쓰이는 것은 heappush, heappop

# 여기서 heap_name은 heap으로 사용할 리스트 이름이다.
heappush(heap_name, value) # value를 heap으로 push
heappop(heap_name) # heap에서 min값 pop하고 반환, 만약 비어있을 때 호출하면 IndexError

heap[0]은 항상 최솟값을 보장

최소힙

heappush, heappop을 그대로 쓰면 된다.

import heapq

heap = []

for i in range(1, 6): # heap에 1~5 push
	heapq.heappush(heap, i)

for i in range(5): # 작은 숫자부터 1,2,3,4,5가 출력된다.(출력과 pop을 동시에)
	print(heapq.heappop(heap))

최대힙

하지만 최대힙은 다르다. heapq에서는 최대힙을 제공하지 않는다. 그래서 보통 부호를 변경하는 방법으로 최대힙을 구현한다.
1) 부호 바꿔서 최소힙에 넣기 2) pop할 때 부호 바꾸기

import heapq

heap = []
values = [1,5,3,2,4]

# 1) 부호 바꿔서 최소힙에 넣기
# heap 내에는 -1~-5까지 존재
for value in values:
	heapq.heappush(heap, -value)
	print(heapq)

# 2) pop할 때 부호 바꾸기
# 5,4,3,2,1이 출력된다. 즉, 큰 숫자부터 출력이 된다.
for i in range(5):
	print(-heapq.heappop(heap))

참고) https://velog.io/@yyj8771/Python-heapq%EB%A5%BC-%EC%9D%B4%EC%9A%A9%ED%95%9C-%EC%B5%9C%EC%86%8C-%ED%9E%99-%EC%B5%9C%EB%8C%80-%ED%9E%99

---

코드

import sys
import heapq
input = sys.stdin.readline

heap = []
n = int(input())
for _ in range(n):
    a = int(input())
    if a == 0: # min 출력, pop
        if heap:
            print(heapq.heappop(heap))
        else:
            print(0)
    else:
        heapq.heappush(heap, a)

+) 이 코드에서

import sys
input = sys.stdin.readline

이걸 안쓰면 시간초과난다.