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
Author And Source
이 문제에 관하여(TIL-065 | python_heapq module), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lck0827/TIL-065-pythonheapq-module저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)