힙큐(heapq)에 대하여

최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리

 

트리는 root node에서 밑으로 가지를 뻗어나가는 형태의 자료구조로

 

binary tree인 이진 트리는 최대 2개까지만 자식 노드를 가진다

 

최소힙은 부모 node가 자식 node보다 항상 작은 binary tree

 

최대힙은 부모 node가 자식 node보다 항상 큰 binary tree

 

 

heap은 배열로 구현되며 파이썬에서는 list로 만들어진다

 

import heapq를 통해 파이썬에서 heapq 관련 함수 사용가능

 

기존 리스트를 heapq로 만들려면 heapify()를 이용

 

heap2 = [50,10,20]

heapq.heapify(heap2)

print(heap2)
[10,50,20]

 

혹은 빈 리스트를 생생한 후에 heappush(heap, element) 형태로 인자를 넘겨준다

 

import heapq

heap = []

heapq.heappush(heap,50)

heapq.heappush(heap,10)

heapq.heappush(heap,20)

print(heap)
[10,50,20]

 

heappop()을 이용해서 가장 작은 원소를 제거하면서 그것을 결과로 return함

 

result = heapq.heappop(heap)

print(result)

print(heap)

10
[20,50]

 

k번 반복 호출하면 k번째 최솟값/최댓값을 찾을 수 있음

 

파이썬의 heapq모듈은 최소 힙으로 구현되어서 최대 힙을 구현하기 위해 약간의 트릭을 사용함

 

heappush()로 힙에 원소를 추가할 때 (-item,item)으로 원소를 추가하면 튜플의 첫번째 원소인 -item을 기준으로 힙을 구현함

 

heapq가 최소 힙으로 구현되는데 -item으로 - 부호로 변환해서 정렬하면 최솟값 정렬이 최댓값 정렬로 바뀜

 

heap_items = [1,3,5,7,9]

max_heap = []

for item in heap_items:
    
    heapq.heappush(max_heap, (-item,item))
    
print(max_heap)

[(-9,9), (-7,7), (-3,3), (-1,1), (-5,5)]

 

여기서 heappop을 하면 가장 작은 원소인 (-9,9)를 반환하는데 여기서 첫번째 원소인 9를 가져오면 최댓값을 반환한다

 

 

max_item = heapq.heappop(max_heap)[1]

print(max_item)
9

 

 

참고

 

https://developer-alle.tistory.com/321

[파이썬] 힙큐(heapq)

 

https://littlefoxdiary.tistory.com/3

[Python] 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기