[백준] 11279 - 최대힙 [Python(파이썬)]

문제

www.acmicpc.net/problem/11279

11279번: 최대 힙

풀이

파이썬에 내장된 힙(heap)모듈을 사용하여 풀 수 있다. 이것은 기본적으로 min heap이므로 약간의 처리가 필요하다. 삽입 시 리스트의 형태([-x, x])로 삽입하는 방식으로 max heap을 구현할 수 있다. 파이썬에서 정렬은 첫번째 원소를 기준으로 이루어지기 때문이다.

 

코드

import sys
import heapq as hq

def get_max(x):
    if heap:
        _max = hq.heappop(heap)
        return _max[1]
    else:
        return 0

def insert_num(x):
    hq.heappush(heap, [-x, x])

n = int(sys.stdin.readline().strip())
heap = []

for _ in range(n):
    x = int(sys.stdin.readline().strip())
    if not x:
        print(get_max(x))
    else:
        insert_num(x)