힙이란 우선순위큐(Priority Queue)를 이진 트리로 구현한 자료구조 입니다. 힙의 삽입, 삭제 연산은 $O(\log n)$의 시간복잡도를 가집니다.

힙은 파이썬 내장모듈인 heapq를 이용해서 손쉽게 구현할 수 있습니다.

import heapq

arr = [4, 5, 6, 7, 9, 8, 3, 1, 2]
heapq.heapify(arr)

print(heapq.nsmallest(3, arr)) # 1 2 3
print(heapq.nlargest(3, arr)) # 7 8 9

while arr:
    print(heapq.heappop(arr)) # 1 2 3 4 5 6 7 8 9

data = [5, 4, 6, 3]
for d in data:
    heapq.heappush(arr, d)
    print(arr[0]) # 5 4 4 3

파이썬의 heapq 모듈은 최소힙만 지원하므로 최대힙을 구현하기 위해서는 각각의 값들에 -를 붙여서 넣어주고, pop 연산을 수행할 때 다시 -1을 곱해주는 방법을 사용합니다.

또한 Key & Value 페어를 통해 힙을 구현할 수도 있습니다.

keys = [1, 2, 3]
values = ['hello', 'python', 'world']
data = list(zip(keys, values))
h = []
for k, v in data:
    # key, value 순서대로 넣어줌
    heapq.heappush(h, (k, v))

while h:
    k, v = heapq.heappop(h)
    print("Key: %d, Value: %s" % (k, v)) # Key: 1, Value: hello / Key: 2, Value: python / Key: 3, Value: world /