[TIL] 힙큐 heapq Python

다익스트라를 공부하는데 코드 구현에서 heapq 가 나와서 정리한다 

힙큐 heapq

최대값과 최소값을 찾는 연산에 특화된 완전 이진 트리 
우선순위 큐를 위해 만들어 자료 구조이다 

 

최소힙 Min Heap 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 것

최대힙 Max Heap 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 것 

힙큐는 최소힙 자료 구조를 이용한다 

 

heapq 메서드

1. heapq.heapify(iterable)

원래 있던 리스트를 힙으로 사용하기 위해 힙화 (heapify) 진행

Heapify 의 디폴트 값은 최소힙이다

import heapq

heap2 = [5, 2, 1, 3, 8]
heapq.heapify(heap2)
print(heap2) # 결과 출력 [1, 2, 5, 3, 8]

2. heapq.heappush(heap, item)

item 을 heap 리스트에 넣는다 

heappush 를 이용하면 Heapify 된 상태를 유지하면서 값을 넣을 수 있다

import heapq

heap_q = []
heapq.heappush(heap_q, 5) # heap_q = [5]
heapq.heappush(heap_q, 2) # heap_q = [2, 5]
heapq.heappush(heap_q, 1) # heap_q = [1, 5, 2]
heapq.heappush(heap_q, 3) # heap_q = [1, 3, 2, 5]
heapq.heappush(heap_q, 8) # heap_q = [1, 3, 2, 5, 8]

print(heap_q) # 결과 출력 [1, 3, 2, 5, 8]

3. heapq.heappop(heap)

Heap 에서 가장 작은 원소를 삭제하고 값을 반환한다 (루트 노드의 값을 반환)

heap_pop = heapq.heappop(heap_q)
print(heap_pop) # 결과 출력 1
print(heap_q)   # 결과 출력 [2, 3, 8, 5]

루트 노드 1 을 제거하면 힙의 구조가 깨지므로, 마지막 노드를 루트로 올리고

이동된 루트에서 자식 노드와 비교하여 최소 힙 또는 최대 힙의 특성을 유지하도록 힙 구조를 다시 조정한다