11279 - 최대 힙 (silver 2)

"""
11279 - 최대 힙 (silver 2) 
"""
import sys
import heapq

input = sys.stdin.readline

heap_list = []
n = int(input().rstrip())
for _ in range(n):
    x = int(input().rstrip())
    if x == 0:
        if not heap_list:
            print("0")
        else:
            print(heapq.heappop(heap_list)[1])
    else:
        heapq.heappush(heap_list, (-x, x))

최대 힙 (우선순위 큐) / heapq 모듈

 

최대 힙을 만들 때는 트릭 필요

heapq 모듈은 최소 힙을 만들기에 push할 때 튜플 형식 (-x, x) 으로 작성한다

힙 리스트에는 튜플의 첫번째 원소끼리만 비교를 해서 최소값인 수가 맨 앞에 오는 구조

ex ) heap_list = [(-8, 8), (-6, 6), (-4, 4), (-2,2)]