[최소 힙] 파이썬 코드 및 그림 설명

Python 3.10

 

파이썬에서 힙 사용 예제입니다.

import heapq

N = [3,6,1,8,2,4,11,9]
heap = []

for i in N:
    heapq.heappush(heap, i)
    print (f'{heap=}')
    
# 실행결과
heap=[3]
heap=[3, 6]
heap=[1, 6, 3]
heap=[1, 6, 3, 8]
heap=[1, 2, 3, 8, 6]
heap=[1, 2, 3, 8, 6, 4]
heap=[1, 2, 3, 8, 6, 4, 11]
heap=[1, 2, 3, 8, 6, 4, 11, 9]

N 배열의 요소를 하나씩 heap에 추가하는 예제입니다.

 

위의 각 요소를 실행한 결과를 그림으로 보면 아래와 같습니다.

최소 힙이기 때문에 낮은 숫자가 위에 위치하여야 하며, 부모 노드의 숫자는 자식 노드의 숫자보다 작아야 합니다.

따라서 N[2] 또는 N[4]같은 경우 자식 노드에 추가된 숫자가 부모 노드의 숫자보다 작으므로 교환을 합니다.

 

그리고 위의 실행 결과 중 최종 결과가 아래와 같이 출력되는 이유는 heapq는 배열로 구성되기 대문입니다.

heap=[1, 2, 3, 8, 6, 4, 11, 9]

 

아래는 heapq의 소스코드 중 구성에 관한 설명입니다.

아래 내용을 보시면 k[0]이 제일 상단에 위치하고 그 아래에 자식 노드로 k[1], k[2]가 연결됩니다.

그리고 k[1]의 자식 노드로 k[3], k[4]가 추가됩니다.

 

The numbers below are `k', not a[k]:

 

                                   0

 

                  1                                 2

 

          3               4                5               6

 

      7       8       9       10      11      12      13      14

 

    15 16   17 18   19 20   21 22   23 24   25 26   27 28   29 30

 

heapq의 각 기능과 상세한 내용은 추후 다시 다루어보겠습니다.