[백준] 1927번 : 최소힙 (python 파이썬)

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

1927번: 최소 힙

 

문제정리 :  N번 수행하는동안 자연수 x가 주어지면 배열에 추가, 0인 x가 주어지면 최솟값 출력 및 제거(pop)

 

# heapq 및 sys import
import heapq
import sys 
h = [] #배열 생성
n = int(sys.stdin.readline()) #n값 받기
for i in range(n): #n번 수행
    x = int(sys.stdin.readline()) #x값 받기
    if x == 0: #x가 0일 때
        if len(h) == 0: #배열에 아무것도 없을 경우
            print(0)
        else:
            result = heapq.heappop(h) #최솟값 출력 및 제거
            print(result)
    else: #x가 자연수일 경우
        heapq.heappush(h, x) #배열에 값 넣기

 파이썬 heapq 모듈을 통한 heapq 알고리즘을 이용한다.

 

heapq.heappush(heap, item) : item 을 heap에 추가 [O(log n)]

heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출된다. [O(1)]

heapq.heapify(x) : 리스트 x를 heap으로 변환 [in linear time, O(N)]