[백준] 최대 힙, 최소 힙 파이썬

파이썬 힙 자료구조 heapq

heapq 모듈을 사용하여 priority queue를 구현할 수 있다.

import heapq

heapq.heappush(heap, item) 
# item을 heap에 추가

heapq.heappop(heap) 
# heap에서 가장 작은 원소를 pop하고, 비어 있는 경우 idexError가 호출됨

heapq.heapify(x) 
# 리스트 x를 heap으로 변환

 

---

최대힙

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

import sys
import heapq

N = int(sys.stdin.readline())

max_heap = []
for i in range(N):
    x = int(sys.stdin.readline())
    if x == 0:
        if max_heap:
            print(-heapq.heappop(max_heap)) # 최대힙으로 사용하기 위해 - 사용
        else:
            print(0)
    else:
        heapq.heappush(max_heap, -x) # 최대힙으로 사용하기 위해 - 사용

 

---

최소힙

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

import sys
import heapq

N = int(sys.stdin.readline())

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