최대힙

문제 포인트

• 최소힙을 사용하여 최대힙으로 구현해보자
• heapq 자료구조는 무조건 최솟값만을 위한 자료구조이기 때문에 이 자료구조를 사용하여 최솟값을 판별하기 위해서는 약간의 트릭이 필요하다.
• 바로 -로 push하는 것.
  • 3,4 있으면 3이 더 작은 숫자지만 -3, -4가 있으면 -4가 더 작은 숫자가 된다.
  • 이렇게 push하고 마지막에 pop()하는 단계에서 - 붙여서 pop()하주면 그게 가장 큰 값이다.

solution

"""
힙큐 자료구조는 무조건 최소힙을 만들어내기 때문에
최대힙을 사용하기 위해서는 - 값으로 push하여 - 값을 붙인 상태로 출력하면 최댓값 출력 가능.
"""
tmp = []
while True:
    num = int(input())

    if num == -1:
        sys.exit()
    elif num == 0:
        if len(tmp) == 0:
            print(-1)
        else:
            print(-hq.heappop(tmp))
    else:
        hq.heappush(tmp, -num)