데이터 정렬을 위해 힙큐 내장 모듈에 대해 알아보자.
1) 추가, 삭제
# 최소 힙
import heapq
heap = []
# 추가
heapq.heappush(heap, 7)
heapq.heappush(heap, 1)
heapq.heappush(heap, 0)
heapq.heappush(heap, 2)
print(heap)
# 결과 : [0, 2, 1, 7]
# 삭제
print(heapq.heappop(heap))
print(heap)
# 결과 : 0
# [1, 2, 7]
2) 리스트를 힙으로 변환
# 리스트 -> 힙 변환
li = [2, 6, 1, 3, 5]
heapq.heapify(li)
print(li)
# [1, 3, 2, 6, 5]
3) 최대 힙
모듈은 최소 힙으로 동작한다.
각 값에 우선 순위를 정해서, 최대 힙으로 만들어보자.
# 최대 힙
li = [2, 6, 1, 3, 5]
heap = []
for x in li:
heapq.heappush(heap, (-x, x)) # (우선 순위, 값)
print(heap)
# [(-6, 6), (-5, 5), (-1, 1), (-2, 2), (-3, 3)]
4) 주의 사항
인덱스 0번째에 가장 작은 원소가 있더라도,
인덱스 1번째에 그 다음으로 작은 원소가 있다고 보장할 수 없다.
왜냐하면 힙은 최소값을 인덱스 0에 위치시키는 것에만 관심있기 때문이다.
(최댓값의 경우 반대로 생각하면 된다.)