최대 힙(백준 11279번)

문제

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

나의 풀이

import heapq, sys

N=int(input())

MaxHeap=[]

for i in range(N):
    I=int(sys.stdin.readline().strip())
    if I==0:
        if MaxHeap:
            print(-heapq.heappop(MaxHeap))
        else:
            print(0)
    else:
        heapq.heappush(MaxHeap,-I)

• heapq를 사용해서 구현했다. (heapq사용하는 방법을 정확하게 파악하자)
  • MaxHeap.pop()과 같은 명령어를 사용하면 heap구조가 풀린다. 따라서 heapq.heapify()로 다시 heap구조로 만들어주어야 한다.
  • heappush는 빈 list에 처음 사용해야 하고, 만약 빈 list가 아니라면 heapify를 써줘야 함
• heapq는 MinHeap인데, -를 붙여주어 MaxHeap처럼 동작하도록 했다.