[백준] 1927 번 최소 힙(python)

1. 문제

https://www.acmicpc.net/problem/1927

2. 풀이

• 파이썬의 힙 모듈을 사용하였다.
• heappush(heap, item) 형태이며 디폴트는 최소 힙이다.

📚 힙이란?
여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 이진 트리
데이터의 삽입과 삭제는 모두 O(logN)이 소요된다.

파이썬에서 힙 모듈은?

1. heapq.heappush(heap, item)
   힙 불변성을 유지하면서, item 값을 heap으로 푸시합니다.
2. heapq.heappop(heap)
   힙 불변성을 유지하면서, heap에서 가장 작은 항목을 팝하고 반환합니다. 힙이 비어 있으면, IndexError가 발생합니다. 팝 하지 않고 가장 작은 항목에 액세스하려면, heap[0]을 사용하십시오.
3. heapq.heappushpop(heap, item)
   힙에 item을 푸시한 다음, heap에서 가장 작은 항목을 팝하고 반환합니다. 결합한 액션은 heappush()한 다음 heappop()을 별도로 호출하는 것보다 더 효율적으로 실행합니다.
4. heapq.heapify(x)
   리스트 x를 선형 시간으로 제자리에서 힙으로 변환합니다.

3. 코드

import heapq
import sys

n = int(sys.stdin.readline())
heap = []

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