[Python] BOJ/백준 1927번 최소 힙

[문제]

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

1927번: 최소 힙

 

[풀이]

힙(Heap)?

힙은 완전 이진트리로 수의 집합에서 가장 작은 수나 가장 큰 수만을 자주 꺼내올 때 유용한 자료구조이다.

항상 자식은 두개밖에 없으며, leaf의 가장 왼쪽부터 값을 채운다.

힙은 크게 최소힙과 최대 힙 두 가지가 있다. 최소 힙은 가장 작은 값이 루트이고, 최대 힙은 가장 큰 값이 루트이다.

 

힙은 완전 이진트리이지만 코드를 구현하기 위해서는 배열로 접근하는 생각을 해봐야 한다. 

 

다른 분이 힙에 관해서 잘 정리해놓은 블로그

[자료구조] 그림으로 쉽게 보는 힙(Heap) 개념과 코드

---

처음에는 파이썬에 heapq 모듈이 있는지 모르고 deque를 사용하는 문제인 줄 알았지만 heapq 모듈을 이용하면 쉽게 풀 수 있는 문제이다.

 

[코드]

import sys
import heapq

if __name__ == '__main__':
    heap = []
    for _ in range(int(sys.stdin.readline())):
        x = int(sys.stdin.readline())
        if x == 0:
            if not heap:
                print(0)
            else:
                print(heapq.heappop(heap))
        else:
            heapq.heappush(heap, x)