[백준 1927][파이썬] 최소 힙. 파이썬 heapq 모듈 사용법 (우선순위 큐)

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

1927번: 최소 힙

우선순위 큐를 사용하여 푸는 문제이다.

 

우선순위 큐의 삽입, 삭제 시간 복잡도는 O(log N)이다.

 

파이썬에서 우선순위큐인 heapq 모듈을 제공한다.

 

heapq의 경우 사용방법이 특이한데 따로 리스트를 만들고 이 리스트를 heapq 메소드의 인자로 사용해야 한다.

 

1. 삽입 : heapq.heappush( list, value )

import heapq
li=[]
heapq.heappush(li, 10)
heapq.heappush(li, 20)
heapq.heappush(li, 15)

 

2. 삭제 : heapq.heappop( list )

 

리스트에 들어있는 값 중 가장 작은 값을 삭제 후 반환한다.

import heapq
li=[]
heapq.heappush(li, 10)
heapq.heappush(li, 20)
heapq.heappush(li, 15)

a=heapq.heappop(li)
b=heapq.heappop(li)
c=heapq.heappop(li)
print(a, b, c)

결과

10 15 20

 

3. 최소 값 얻기 : list[0]

heapq 모듈을 사용하여 리스트에 값을 넣을 때 항상 가장 작은 값이 인덱스 0에 존재한다.

 

참고로 오름차순으로 정렬하는 게 아니다.

 

기본적으로 heapq는 최소 힙이기 때문에 만약 최대 힙으로 바꾸고 싶다면 단순히 값을 넣을 때 음수로 바꾸어서 넣고 값을 뺄 때 양수로 바꾸어서 빼내면 된다.

 

<전체 코드>

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