[Python] heapq

heapq

: 데이터를 정렬된 상태로 저장하기 위해 사용되는 python의 내장 모듈

: 이진트리 기반의 최소 힙(min heap) 자료구조 제공

: min heap을 사용하면 원소들이 항상 정렬된 상태로 추가, 삭제된다 (따라서 가장 작은 값은 언제나 인덱스 0, 루트에 위치)

 

* 사용법

1) 모듈 import

import heapq

 

2) min heap 생성

: 빈 리스트 생성 후 heapq모듈의 함수 호출 시 이 리스트를 인자로 넘겨준다.

heap = []

 

3) heap에 원소 추가

: heappush(리스트, 원소)함수 이용

heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)
print(heap) #[1, 3, 7, 4] : 작은원소부터 정렬되어 추가됨

 

4) heap에서 원소 삭제

: heappop(리스트)함수 이용하여 가장 작은 원소 삭제 후 값 리턴

print(heapq.heappop(heap)) #1 : 삭제한 원소
print(heap) #[3, 4, 7] : 삭제 후 남은 리스트

 

5) 삭제 없이 원소 읽기

print(heap[0])

 

6) 기존 리스트를 heap으로 변환

: heapify(리스트)함수 이용

: 기존 리스트가 직접 변경되는 것

heap = [4, 1, 7, 3, 8, 5]
heapq.heapify(heap)
print(heap) #[1, 3, 5, 4, 8, 7]

 

7) 최대 힙으로 사용

: heapq는 최소 힙 기능만 동작하기 때문에 최대 힙을 사용하려면 주어진 수들에 -를 붙여 만들 수 있다.

nums = [[1,2], [0,5], [2,3]] #[우선순위, 원소]
heap = []

for i in range(len(nums)):
  heapq.heappush(heap, (-nums[i][0], nums[i][1]))  # 우선순위 높은 순서대로 push

while heap:
  print(heapq.heappop(heap)[1])

 

*참고

https://www.daleseo.com/python-heapq/