[파이썬] heapq 힙큐 사용하기

Heapq Document

Python docs homepage

 

 

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)