[BOJ] 1927 최소 힙

1927 최소 힙

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

heapq 모듈 사용법

힙

특정한 규칙을 갖는 트리
최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전 이진 트리를 기본으로 한다.
(완전 이진 트리 : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워진 트리)

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

heapq

• priority queue 알고리즘을 제공한다.
• 내장 모듈임
• 기본적으로 최소 힙

메소드

• heapq.heappush(heap,item) : item을 heapq에 추가
• heapq.heappop(heap) : 가장 작은 원소를 삭제 후 반환, 빈 경우 IndexError 호출
• heapq.heapify(x) : 리스트 x 를 heap으로 변환. 즉, 정렬하는 것

예시:

import heapq
heap = [5,2,3]

heapq.heapify(heap) 
print(heap) #[2, 5, 3]

heapq.heappush(heap,1)
print(heap) #[1, 2, 3, 5]

print(heapq.heappop(heap)) # 1

heapq.heapify(heap)
print(heap) #[2,5,3]

print(heapq.heappop(heap)) #2
print(heap) #[3,5]

참고