[Algo] 6.2 Maintaining the heap property

MAX-HEAPIFY 的用途
這個 subroutine 是用來整理 heap 裡的 element 位置，讓 heap 遵守 max-heap property。這個 subroutine 的 input 是一個 array A 跟一個 array index i。call 這個 subroutine 的時候是假設以 LEFT(i) 跟 RIGHT(i) 為 root 的 subtree 都是標準的 max-heap，我們要做的就是把 A[i] 這個 node 擺到以它為 root 的 subtree 裡面到一個適當的位置。

@{
\proc{Max-Heapify}(A, i)
\li l = \proc{Left}(i)
\li r = \proc{Right}(i)
\li \If l \leq \textit{heap-size}[A] \;\textup{and}\;A[l] > A[i]
\li \;\;\;\;largest = l
\li \Else
\li \;\;\;\;largest = i
\li \If r \leq \textit{heap-size}[A] \;\textup{and}\;A[r] > A[largest]
\li \;\;\;\;largest = r
\li \If largest \not= i
\li \;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[largest]
\li \;\;\;\;\proc{Max-Heapify}(A, largest)
}@

MAX-HEAPIFY 的圖解

MAX-HEAPIFY 的精神
一開始先比較A[i], A[LEFT(i)], A[RIGHT(i)]這三者之間誰是最大的，因為 root 必須是這棵 subtree 中最大的 element，所以我們把這三者最大的 node 拿來當作新的 root，當然 A[i] 就往下跳，變成更小的 subtree 的 root 了。這個 subroutine MAX-HEAPIFY 就得以繼續遞迴的 call 下去，整個過程可以看上圖得知。




MAX-HEAPIFY 的 running time
首先在第 1~9 行裡面都是在找出這三者之間的大小關係，所以我們可以把它的 running time 視為$\Theta(1)$。重點是 recurrsively call MAX-HEAPIFY 這個 subroutine 的 running time。worst-case 發生在整棵 tree 是呈現半滿的狀態，而且這某半邊的 subtree 是棵 complete 的 binary tree，這個時候這某半邊的 subtree 的 size 是整棵 tree 的 $2n/3$。所以我們可以得到這個遞迴式：$T(n) \leq T(2n/3) + \Theta(1)$，根據 master theorem，我們可以知道 $T(n) = O(\lg n) = O(h)$