[백준] 최소 힙

[백준] 최소 힙

---

풀이

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

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

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

import heapq
import sys
n = int(input())
q = []
ans = []
for _ in range(n):
    input_num = int(sys.stdin.readline())
    
    if input_num == 0:
      if not q:
        ans.append(0)
      else:
        ans.append(heapq.heappop(q))
    
    else:
      heapq.heappush(q, input_num)

for res in ans:
    print(res)

---

실수 및 배운 점

• 가장 기본적인 heap에 대한 내용에 대해 정리했다.
  heapq는 최소 힙을 default로 한다. 최소 힙은 가장 위의 값이 작은 값이고 완전 이진 트리를 기본으로 자료구조가 만들어진다.
  이 힙을 통해 우선 순위 큐를 만든다.