[백준 파이썬(python) 11279번 문제 최대힙 ]

문제

설명

파이썬에서는 우선순위 큐 (heapq)는 min-heap(최소힙)이 기본사항으로 되어있는데 이걸 max-heap으로 바꾸는 문제

min-heap: [-1,5,2,4] ===> [-1,2,4,5] ===> -1, 2 ,4 ,5

 

값을 넣을때 - 부호를 붙여주고 빼와서 쓸때 - 부호를 붙여주면 max-heap처럼 사용가능

max-heap : [-1,5,2,4] ===> [1,-5,-2,-4] ===> [-5,-4,-2,1] ===>  5 , 4 , 2 ,-1

 

코드

import sys
import heapq

input = sys.stdin.readline

N = int(input())
li = []
for _ in range(N):
    num = int(input())
    if num == 0:
        if li:
            print(-heapq.heappop(li))
        else:
            print(0)
    else:
        heapq.heappush(li, -num)

max-heap 변환은 튜플을 써서 하는 방법도 있다

변환 꼼수는 언젠가 필요할테니 기억해두자