TIL-065 | python_heapq module

🌈 heapq module

python의 heapq module

• 파이썬 heapq 모듈은 heapq (priority queue) 알고리즘을 제공한다.

• heapq는 내장 모듈로 별도의 설치 작업 없이 바로 사용할 수 있다.

import heapq

• 최소힙으로 구현 되어있기 때문에 최대힙을 구현하기 위해서는 트릭이 필요하다.(ex. y = -x 변환)

heapq 모듈의 활용

• heapq 모듈은 리스트를 최소 힙처럼 다룰 수 있도록 하기 때문에, 빈 리스트를 생성한 후 heapq의 함수를 호출할 때마다 리스트를 인자에 넘겨야 한다.

🙆‍♂️ heapq 모듈 메서드 사용법

✔ heapq.heappush(heap, item) : item을 heap에 추가
✔ heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨.
✔ heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) )

import heapq


# 파이썬의 heapq 모듈읜 최소힙으로 생성된다. 
heap = [] # 빈 리스트 선언

# heapq.heappush(heap, item): item을 heap에 추가
heapq.heappush(heap, 1000)
heapq.heappush(heap, 10)
heapq.heappush(heap, 100)

print(heap) # [10, 1000, 100]

# heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨. 
heapq.heappop(heap)

print(heap) # [100, 1000]

# heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) )
heap2 = [200, 20, 100]

heapq.heapify(heap2) # [20, 200, 100]

최대힙 만들기

• 위에서 언급한 바와 같이 heapq 모듈은 최소힙을 구현하기 때문에 최대힙의 구현을 위해서는 약간의 트릭이 필요하다.

• 구현 방법은 아래의 소스코드와 같다.

# 최대 힙 만들기
heap = [1, 2, 3, 4, 5]
max_heap = []

for item in heap:
    heapq.heappush(max_heap, (-item, item))
print(max_heap) # [(-5, 5), (-4, 4), (-2, 2), (-1, 1), (-3, 3)], 튜플 형태의 힙 구조

max_value = heapq.heappop(max_heap)
print(max_value[1]) # 5 (최댓값 반환)

• 힙 구조화 되지 않은 리스트가 있을 경우, (-item ,item) 의 형태로 heappush를 한다.

• heappop 메서드를 통해 튜플 값을 뽑아내고 그 값의 인덱스 1번 값을 뽑아내면 최댓값이 된다.

📝 Reference

1. https://littlefoxdiary.tistory.com/3
2. https://www.daleseo.com/python-heapq/