[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]
Author And Source
이 문제에 관하여([BOJ] 1927 최소 힙), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kinnyeri/BOJ-1927-최소-힙저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)