[CLRS] [6-3] Building a heap

0. Review

- 이번 챕터에서는 Max-Heap을 만들기 위해 6-2에서 구현했던 max_heapify()를 이용하고자 한다.

- 이를 leaf-node(자식이 없는 노드)부터 시작하여 root-node까지 거슬러 올라가 max_heapify()를 호출하면 된다.

- 이때 leaf-node는 heap에서 다음과 같다. A[n//2 + 1: ] 까지에 해당한다. 

- leaf-node에서 max_heapify()를 호출하더라도 변함없기 때문에 구현할 코드에선 A[n//2] ~A[1]까지만 호출하는 것으로 구현하였다.

 

1. Code

1.1. max_heapify()

def max_heapify(arr,i):

    left_node = 2*i
    right_node = 2*i+1
    
    if (left_node <= len(arr)-1) and arr[left_node] > arr[i]:
        largest = left_node
    
    else:
        largest = i
    
    if (right_node <= len(arr)-1) and arr[right_node] > arr[largest]:
        largest = right_node
    
    if largest != i:
        arr[i],arr[largest] = arr[largest] , arr[i]
        max_heapify(arr,largest)

1.2. build_max_heap()

def build_max_heap(arr):
    for i in range((len(arr)-1)//2 , 0 , -1):
        max_heapify(arr,i)

 

2. 알고리즘 설명

- build_max_heap()에서의 for문을 확인해보면 다음과 같은 루프 불변성(loop invariant)을 사용한다.

--> i에서 max_heapify()를 사용한다면, i+1,i+2...n까지의 노드들은 전부 max_heap을 만족한다.

- 이는 해당 build_max_heap() 함수가 정말 heap을 max_heap으로 만들어 내는지 증명할 수 있게 하는 중요한 성질이 된다.