[11279] 최대 힙 - Python

/* 문제 */
널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.
    1. 배열에 자연수 x를 넣는다.
    2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.

최대 힙을 구현해 보는 문제다. 파이썬의 내장 모듈 heapq를 사용했다.

# 정답 코드
import sys
input = sys.stdin.readline
import heapq

heap = []

n = int(input())
for _ in range(n):
    x = int(input())
    if x == 0:
        if len(heap) == 0:
            print(0)
        else:
            print(-heapq.heappop(heap))
    else:
        heapq.heappush(heap, -x)

1927번 최소 힙 문제에서 힙에 넣고 빼는 값들의 부호만 달라졌다. 부호를 바꿔 대소관계를 역전시켜 저장한 후 꺼낼 때 부호만 다시 돌려놓는 방법이다. 

---

1927, 11279 문제를 풀어보며 힙의 기본적인 사용 방법을 알아봤다. 힙을 적용하여 풀 수 있는 문제들을 더 풀어봐야겠다.