[백준 #1927] 최소 힙

1. 개요

2. 설명 및 풀이

1. 힙(Heap)이란?

   이진 트리 기반의 자료구조로, 부모 노드와 자식 노드 사이에는 항상 대소관계가 정해지는 자료구조를 말한다. 여기서 부모 노드 >= 자식 노드면 최대 힙, 부모 노드 <= 자식 노드이면 최소 힙이다.

   쉽게 말해서 배열 안의 값들이 오름차순(최소 힙)이나 내림차순(최대 힙)으로 정렬되어 있다는 것.

2. 코드

import sys, heapq
input = sys.stdin.readline

n = int(input())
heap = []
for _ in range(n):
    x = int(input())
    if x == 0:
        print(0 if not heap else heapq.heappop(heap))
    else:
        heapq.heappush(heap, x) #최소 힙 구조 사용

Python은 라이브러리로 최소 힙을 지원한다. 그래서 heapq 라이브러리를 상단에 선언해주고, 가져와서 적절히 사용해주면 된다.