최소힙

알고리즘 문제를 풀다보면 가끔 최소힙이라는 자료구조를 이용해야 할 때가 있다.

일단 힙이라는 것은 들어온 순서로 나가는 선입선출 방식의 단순한 자료구조이다.

하지만 최소힙은 들어왔을 때 작은 순서로 나가게 된다. (최대힙도 있다! 원리는 거의 유사하다.)

최소힙의 자세한 원리는 이 블로그에서 잘 설명해주고 있는 것 같다.

 

파이썬에서 어떻게 최소힙을 사용할 수 있을지 백준의 1927번 문제를 풀어보자.

push(넣는다.)와 pop(꺼낸다.)이라는 명령으로 단순하게 작동한다.

아래처럼 가져와서 이용할 때 list를 만들어주고 그것을 push를 할 때 활용한다.

import heapq
from sys import stdin

h = []
count = 0
m = int(stdin.readline().rstrip())
    
for _ in range(m) :
    x = int(stdin.readline().rstrip())
    if x!=0 :
        heapq.heappush(h,x)
        count+=1
    elif x==0 :
        if count == 0 :
            print(0)
            continue
        print(heapq.heappop(h))
        count-=1