파이썬) 최대 힙 - BOJ

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

11279번: 최대 힙

 

힙은 흔히 최소값을 출력하고 제거할 수 있다.

그렇다면 힙을 이용해 최대값을 출력할 수 있을까?

정답은 바로 아래 코드이다

import heapq
import sys

input = sys.stdin.readline

n = int(input())

heap = []

for _ in range(n):
    x = int(input())

    if x == 0:
        if not heap:
            print(0)
        else:
            # 가장 작은(절대값이 가장 큰 값)을 빼내 부등호를 바꿈
            print(-heapq.heappop(heap))

    else:
        # 부등호 바꿔서 저장
        heapq.heappush(heap, -x)

저장과 출력의 부등호를 뒤집어 주면 된다.

만약 [1,2,3,4,5]라는 배열을 최대힙으로 나타낸다면 [-5,-4,-3,-2,-1]이 되고 여기서 heapq.heappop을 한다면 -5가 출력될 것이다. 

그 상태엥서 부등호를 반대로 돌려주면 최대힙이 된다.