[CLRS] [6-2] Maintaining the heap property

0. Review

- 6-1 에서 우리는 Heap을 알아가는 동안 Max-Heap에 대해서 알아보았다.

- 이번 챕터에서는 Max-Heap을 유지하게 해주는 Max-Heapify 에 대해서 알아볼 것이다. 

1. Max-Heapify

- Max-Heapify 절차는 최댓값 힙 속성을 유지한다.

- 입력값은 배열 A, 그리고 배열의 인덱스 i를 받는다.

- Max-Heapify는 LEFT(i), RIGHT(i)로 시작하는 Heap들이 이미 Max Heap이라는 것을 가정한다. 

- 하지만 A[i]가 자식노드보다 작을 경우 Max-Heap을 만족하지 않는다.

- 그래서 A[i]를 아래에 있는 노드로 계속 흘려보내면서 Max-Heap을 만족하게 한다.

- 다음 그림은 Max-Heapify의 동작을 보여준다.

 

- (a)상황을 한번 보자. A[i](8)가 왼쪽노드(14)보다 작기 때문에 위치를 바꿔준 것을 볼 수 있다.

- 하지만, 바꿔주고 나서 왼쪽 Heap이 Max-Heap이라는 것이 자명하지 않기 때문에, 

- 다시 한번 (b),(c) 에서 Max-Heapify를 재귀적으로 사용함을 알 수 있다.

 

2. Max-Heapify Code

- 앞서 설명한 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)

 

3. Time Complexity

- 해당 재귀함수를 점화식으로 나타내면 다음과 같다.

T(n) <= T(2n/3) + theta(1)

- 이를 Master Theorem으로 구하면 

- T(n) = O(log n)이 된다. 

- 이를 토대로 힙정렬은 O(nlogn)이 된다는걸 간접적으로 유추가능하다.