Heapq Document
1. Heap 이란?
힙은 최댓값과 최솟값을 찾는 연산에 특화된 완전 이진트리이다. 힙의 종류로는 최소힙과 최대힙이 있는데, 자료값이 낮은 것이 루트로 오면 최소힙, 자료값이 높은 것이 루트로 오면 최대힙이라고 한다. 이를 이용해 우선순위를 쉽게 정할 수 있다는 장점이 있다.
이런 우선순위 힙을 이용한 대표적인 예로는 우선순위 힙을 사용한 개선된 다익스트라 알고리즘이다.
파이썬에서 힙을 사용하기위해 heapq를 선언하는 방법은 아래와 같다.
import heapq
2. heapq의 메소드
- heapq.heapify(iterable)
원래 있던 리스트를 힙으로 사용하기위해서는 먼저 힙화(heapify)를 진행해야하는데, 위의 메소드를 사용해 쉽게 진행할 수 있다. Heapify의 디폴트값은 최소힙이다.
- heapq.heappush(heap, item)
heappush를 이용하면 Heapify된 상태를 유지하면서 값을 넣을 수 있다.
- heapq.heappop(heap)
루트에 있는 값을 pop한다.
3. 최대힙 만들기
튜플을 (-값, 값)으로 구성하면 첫번째 값인 (-값)에 따라 힙정렬이 진행된다. heappop을 진행할 때 인덱스 1의 값을 취해주면 최대힙을 사용할 수 있다.
import heapq
arr = [3, 2, 4, 1, 7, 5, 6]
heap = []
for i in arr:
heapq.heappush(heap, (-i, i))
print(heap)
while heap:
print(heapq.heappop(heap)[1], end=" ")
결과값
>> [(-7, 7), (-4, 4), (-6, 6), (-1, 1), (-2, 2), (-3, 3), (-5, 5)]
>> 7 6 5 4 3 2 1
4. Heapify된 리스트를 힙정렬하기
리스트를 힙으로 만든 다음, heappop을 통해 순서대로 값을 꺼내 리스트에 append하면 정렬된 리스트를 반환할 수 있다.
import heapq
heap = [3, 2, 4, 1, 7, 5, 6]
heapq.heapify(heap)
sorted_arr = []
while heap:
sorted_arr.append(heapq.heappop(heap))
print(sorted_arr)