BAEKJOON #11279) 최대 힙 (Python)

1927번과 마찬가지로 힙을 구현만 하면 해결되는 문제이지만, 파이썬에는 이미 구현되어있는 heapq 라이브러리가 있기 때문에, 함수(heapq.heappush(heap, value), heapq.heappop(value))를 사용만 해준다.

import heapq
from sys import stdin


n = int(stdin.readline())
heap = list()

for _ in range(n):
    input_num = int(stdin.readline())
    if input_num == 0:
        if heap:
            print(heapq.heappop(heap)[1])
        else:
            print(0)
    else:
        heapq.heappush(heap, [-input_num, input_num])

다만, heapq의 함수들은 기본적으로 최소 힙을 구현하기 때문에, 최대 힙을 만들기 위해서는 push할 때 -1을 곱하여 힙에 넣어준다. (마이너스를 붙이면 가장 큰 값이 가장 작은 값이 되어 최상위 노드에 위치되기 때문에)리스트에 마이너스를 붙인 값과 원래 값을 리스트 형태로 넣어주어서 pop하여 print할 때는 저장된 리스트의 1번 인덱스를 출력하여 원래 값이 출력되도록 한다.