[Python/기초] heap

heapq 모듈은 힙(heap) 자료구조를 구현하는데 사용되는 파이썬 내장 모듈입니다. 힙은 부모 노드가 자식 노드보다 항상 작거나 큰 값을 가지는 이진 트리 구조를 가진 자료구조로서, 최소 힙(min heap) 또는 최대 힙(max heap)으로 사용될 수 있습니다. heapq 모듈은 주로 리스트를 사용하여 힙을 구현하며, 이 리스트는 항상 힙의 특성을 만족하도록 유지됩니다.

아래는 heapq 모듈에서 제공하는 주요 함수들입니다:

 

heapify(iterable): 주어진 iterable을 힙으로 변환합니다. 시간 복잡도는 O(n)입니다.

import heapq

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(data)
print(data)  # [1, 1, 2, 3, 3, 9, 4, 6, 5, 5, 5]

 

heappush(heap, element): 힙에 원소를 추가합니다.

import heapq

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

heapq.heappush(data, 0)
print(data)  # [0, 1, 2, 3, 1, 9, 4, 6, 5, 5, 3, 5]

 

heappop(heap): 힙에서 가장 작은(또는 가장 큰, 최대 힙의 경우) 원소를 제거하고 반환합니다.

 

import heapq

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

smallest = heapq.heappop(data)
print(smallest)  # 1
print(data)      # [1, 3, 2, 5, 5, 9, 4, 6, 5, 3]

 

heappushpop(heap, element): 힙에 원소를 추가한 후, 가장 작은(또는 가장 큰) 원소를 제거하고 반환합니다.

 

import heapq

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

result = heapq.heappushpop(data, 0)
print(result)  # 0
print(data)    # [1, 3, 2, 5, 5, 9, 4, 6, 5, 3]

 

heapreplace(heap, element): 가장 작은(또는 가장 큰) 원소를 제거한 후, 새로운 원소를 추가합니다.

import heapq

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

result = heapq.heapreplace(data, 0)
print(result)  # 1
print(data)    # [0, 3, 2, 5, 5, 9, 4, 6, 5, 3]