Heapq 알고리즘 개념 및 활용방법 정리

√ Heap 데이터 구조란?

: 최대/최소값 연산에 용이한 이진트리구조의 데이터 구조

 

Heap의 종류는 부모노드가 최대값을 가지고 자식노드는 그 보다 작은 값을 가지는 Max Heap과

반대로 자식노드가 부모노드보다 큰 값을 가지는 Min Heap 2가지가 있습니다

 

바로 여기서 heapq 모듈은  Min Heap 기능을 가지는 알고리즘에 해당합니다

Source: https://www.geeksforgeeks.org/heap-data-structure/minheapandmaxheap/

 

√ Heapq 모듈 기능 정리

import heapq   : heapq사용을 위해서는 모듈 import가 선행되어야 합니다

 

heapq.heapify(list) : list를 heap으로 변환시킵니다 → Heap으로 변신

import heapq

l = [3,5,2]
heapq.heapify(l)

>> [2,3,5]

 

 

heapq.heappush(heap,element) → Heap에 요소 추가

 : heap에 요소를 insert 할때 사용되며, 요소를 추가하면 min heap은 재정렬됨 (힙구조유지)

 

heapq.heappop(heap) → Heap에서 최소값 삭제/추출

: heap에서 가장 최소값을 뽑아서 return하는 기능. 요소를 pop해도 min heap은 재정렬됨 (힙구조유지)

 

heapq.heappush(l,8)
>> [2,3,5,8]

heapq.heappop(l)
>> 2

 

만약에 push와 pop을 한번에 하고 싶다면?

 

heapq.heappushpop(heap,element) → Heap에 요소 추가하고 최소값 뽑고!

 

heapq.heapreplace(heap,element) → Heap에 최소값 뽑고! 요소 추가하고!

 

import heapq
 
l1 = [5, 1, 9, 4, 3]
l2 = [5, 7, 9, 4, 3]
 
heapq.heapify(li1)
heapq.heapify(li2)
 
print(heapq.heappushpop(l1, 2))
> 요소를 추가하고 최소값을 뽑았으므로 2가 반환됨

print(heapq.heapreplace(l2, 2))
> 최소값을 뽑고 요소를 추가하므로 기존 l2의 최소값인 3이 반환됨

 

이제 큰 / 작은 요소를 n개 추출하고 싶다면?

 

heapq.nlargest(k, iterable, key = None) → Heap에서 n개의 가장 큰 요소로 구성된 리스트를 찾고 싶다면!

 

heapq.nsmallest(k, iterable, key = None) → Heap에서 n개의 가장 작은 요소로 구성된 리스트를 찾고 싶다면!

 

import heapq

ex = [6, 7, 9, 4, 3, 5, 8, 10, 1]

heapq.heapify(ex)

heapq.nlargest(3,ex)
> [10,9,8]

heapq.nsmallest(3,ex)
> [1,3,4]

 

 

번외로 최소힙을 지원하는 heapq를 이용해서 최대 힙을 만드는 코드를 살펴보겠습니다

import heapq

def heapsort(iterable):
	h = []
    result = []
    
    for i in iterable:
    	heapq.heappush(h, -i)
        
    for i in range(len(h)):
    	result.append(-heapq.heappop(h))
    return result

heapsort를 만드는 방식은 min heap과 크게 다르지 않지만, 음수 부호를 통해서 최대힙 리스트를 반환하도록 했습니다

 

 

---

 

 

Source:

 https://www.geeksforgeeks.org/heap-data-structure/minheapandmaxheap/

Heap Data Structure - GeeksforGeeks

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

heapq — 힙 큐 알고리즘 — Python 3.10.7 문서

https://www.geeksforgeeks.org/heap-queue-or-heapq-in-python/

Heap queue (or heapq) in Python - GeeksforGeeks