파이썬의 heapq 모듈

https://docs.python.org/ko/3.7/library/heapq.html

 

힙큐는 최솟값(또는 최댓값)을 계속 뽑아내야 할 때 사용할 수 있습니다.
한 번 정렬해 놓고 하나씩 뽑으면 되지 않냐? 맞습니다. 

 

하지만 계속 새로운 값들이 추가된다면?
새로운 값들이 추가될 때마다
최솟값을 찾기 위해 원소를 전체를 검색해주거나
정렬을 해야 합니다. 느립니다. 

 

이런 경우에 사용하는 것이 힙큐입니다. 

 

힙큐는 리스트와 트리의 장점을 모두 사용합니다.

1. 트리 구조를 사용합니다.  
요소 삽입 및 최솟값(또는 최댓값)의 제거 시 발생하는 요소의 검색 및 스왑의 회수가
일반적인 리스트를 사용할 때보다 현저히 작습니다. 

2. 리스트를 사용합니다.
완전 이진트리는 리스트로 코딩할 수 있습니다. 
리스트가 클래스보다 빠릅니다. 

 

---------------------------------------------------

 

먼저 heap이라는 자료구조를 알아야 하는데요. 
나무위키에서 그림을 보시는 게 좋습니다. 
https://namu.wiki/w/%ED%9E%99%20%ED%8A%B8%EB%A6%AC

 

이진 검색 트리 / 힙 트리

 

제가 설명드린 이진 검색(탐색) 트리와는 좀 다릅니다.
이진 검색 트리는 좌우로 크고 작음을 나누는데, 힙은 위아래로 나눕니다.
https://comdoc.tistory.com/entry/19-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC%EC%99%80-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC-%EA%B2%80%EC%83%89-%ED%8C%8C%EC%9D%B4%EC%8D%AC?category=800088

 

생각해 보면 이진 '검색' 트리는 이진 '검색'에 최적화되어 있고.. 
힙은 연속적으로 '최댓값' 또는 '최솟값'을 찾는데 최적화되어 있음을 알 수 있습니다. 
위아래, 좌우의 차이일 뿐인데 결과적으로 이런 차이가 나다니... 꽤 재미있습니다. 

 

최소 힙 / 최대 힙

 

힙은 특수한 이진트리입니다.

 

완전 이진트리(Complete Binary Tree, 부모부터 자식까지, 좌에서 우로 꽉꽉 채운 이진 트리)이며,
부모는 자식들보다 항상 작거나(최소 힙) 큽니다(최대 힙). 

 

따라서 항상 루트가 최소(최소 힙) 또는 최대(최대 힙)가 됩니다. 
다만 (최소 힙에서) 루트는 최소지만, 
트리의 끝(마지막 레벨 가장 우측 노드)은 최대가 아닐 수 있습니다. 

(그림을 보면 쉽게 이해가 됩니다.
위아래 대소관계만 고려하기 때문입니다. )

(트리의 좌우는 고려하지 않습니다.
좌우까지 맞추면 다른 정렬법과 차이가 없...)

파이썬의 heapq 모듈은 최소 힙(min heap, 루트가 최소)입니다. 

 

힙과 리스트

 

힙은 완전 이진트리(부모부터 자식까지, 좌에서 우로 꽉꽉 채운 이진 트리)이기 때문에 
list로 표현할 수 있습니다. 당연한 이야기지만 클래스보다 리스트의 속도가 빠릅니다. 
그래서 파이썬의 heapq 모듈은 list를 이용합니다. 

 

어떤 식이냐면...

 

루트는 [0], 루트의 왼쪽 자식은 [1] 오른쪽 자식은 [2]이라고 할 때,
[1]의 왼쪽 자식은 [3], 오른쪽 자식은 [4],
[2]의 왼쪽 자식은 [5], 오른쪽 자식은 [6] ........

 

즉 [x]의 왼쪽 자식은 [2x+1] 오른쪽 자식은 [2x+2]으로 정리할 수 있습니다. 

 

힙의 사용

 

heap 자료구조는 우선순위 큐에 사용할 수 있습니다. 
파이썬의 PriorityQueue(우선순위 큐) 모듈은 heapq 모듈을 사용하여 만들었습니다. 
https://www.daleseo.com/python-priority-queue/

 

힙의 구현

 

이진 탐색 트리를 구현했기 때문에.. 
하라면 못할 것도 없지만.. 

 

힙의 구현은 생략하겠습니다. 
나무 위키의 그림을 보시면 됩니다. 

 

파이썬에서는 heapq를 쓰면 되기 때문에
위 내용 정도만 이해하면
사용하시는데 별 문제가 없을 것 같습니다. 

 

---------------------------------------------------

 

요소를 삽입할 때는 heappush, 최솟값을 찾을 때는 heappop입니다. 

>>> from heapq import *
>>> heap=[]
>>> heappush(heap, 4)
>>> heappush(heap, 4)
>>> heappush(heap, 3)
>>> heappush(heap, 2)
>>> heappush(heap, 7)
>>> heappush(heap, 4)
>>> heap
[2, 3, 4, 4, 7, 4]
>>> heappop(heap)
2
>>> heappop(heap)
3
>>> heappop(heap)
4
>>> heappop(heap)
4
>>> heappop(heap)
4
>>> heappop(heap)
7
>>> heappop(heap)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: index out of range

 

기존 배열을 heap으로 바꿀 수도 있습니다. heapify

>>> a = [1,2,3,4,5,6,7,8,4,4,4,4,4]
>>> heapify(a)
>>> a
[1, 2, 3, 4, 4, 4, 7, 8, 4, 4, 5, 4, 6]

 

최대 힙을 쓰려면 튜플을 응용합니다. 

from heapq import *

nums = [2, 4, 1, 5, 4]
heap = []

for num in nums:
    heappush(heap, (-num, num))

print(heap)  # [(-5, 5), (-4, 4), (-1, 1), (-2, 2), (-4, 4)]

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

 

heappushpop과 heapreplace도 있습니다. 

 

heappushpop은 heappush 후 heappop 하는 데
따로 하는 것보다 효율적이라고 합니다. 
이 경우 push 하는 값을 포함해서 최솟값이 나오겠죠?

 

heapreplace는 heappop 후 heappush 하는 데 역시 더 효율적이라고 합니다. 
push 되는 값 보다, pop 되는 값이 더 클 수 있습니다. 
또, pop을 먼저 하기 때문에 리스트가 비었을 경우 인덱스 에러가 발생할 수 있습니다.)
('heappoppush 가 더 직관적이지 않나?'라는 생각이 드는군요.)

 

heapify 한 뒤 heappop 하는 것을 heap 정렬이라고 합니다. 

def heap_sort(nums):
    from heapq import heapify, heappop
    heapify(nums)
    # print(nums)
    sorted_nums = []
    while nums:
        sorted_nums.append(heappop(nums))
    return sorted_nums


print(heap_sort([2, 4, 1, 7, 3, 8, 5, 4, 4, 4]))