[백준/ 파이썬] 11279 최대 힙

벡준 11279 최대 힙

이번에 풀어볼 문제는 우선순위큐를 활용한 최대 힙 문제입니다.
이 문제는 우선순위큐를 활용해서 풀 수 있습니다.
큐는 기본적으로 선입선출의 형태를 가지고 있습니다. 먼저 들어온 값이 먼저 나가는 구조입니다.
우선순위큐는 먼저 들어온 값이 먼저 나가는 것이 아니라, 우선순위가 높은 값부터 먼저 나가는 구조입니다.
보통 우선순위큐는 힙으로 구현합니다.

파이썬에서는 heapq라는 모듈을 제공하기 때문에 이를 이용해서 문제를 풀어보겠습니다.
파이썬에서는 기본적으로 최소힙을 제공합니다. 문제는 최대힙을 요구하기때문에 우리는 최대힙으로 만들어야 합니다.

최대힙으로 만들수있는 방법은 여러 방법들이 있겠지만, 약간의 트릭을 이용해보겠습니다.
우리가 힙에 들어갈 갑들에 -1을 곱해서 최소힙을 만들어 준다음에, pop을 할때는 다시 -1을 곱해주면 최대힙처럼 작동하게 됩니다.

코드는 다음과 같습니다

import sys
import heapq

input = sys.stdin.readline

def max_heap(value):
    heapq.heappush(h, -value)
def heap_delete():
    res = heapq.heappop(h)
    res *= -1
    print(res)

n = int(input())
h = []
for _ in range(n):
    order = int(input())
    if order == 0:  #가장 큰 값 출력하고, pop
        if len(h) == 0:
            print("0")
        else:
            heap_delete()
    else:   #heap에 값을 추가
        max_heap(order)