[백준] 1972. 최소힙 (heapq 알아두기)

힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리

힙 property : A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소 관계가 성립한다

• 최소 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙
• 최대 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

• heapq.heappush(heap, item) : item을 heap에 추가
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨. 
• heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) )

import heapq
import sys
n=int(sys.stdin.readline())
heap=[]
for i in range(n):
    x=int(sys.stdin.readline())
    if x==0:
        if len(heap)==0:
            print("0")
        else:
            num=heapq.heappop(heap)
            print(num)
    else:
        heapq.heappush(heap,x)