[Algo] 6.4 The heapsort algorithm

heapsort的原理
我們有了 BUILD-MAX-HEAP 這個 subroutine 之後，因為 max-heap property，A[1] 一定是最大的 element，所以拿掉 A[1] 之後，我們再次把它建構成一個 max-heap 就可以得到第二大的 element，藉由這樣的方法我們就可以依序得到由大到小的排序了。


heapsort 的 pseudocode
@{
\proc{Heapsort}(A)
\li \proc{Build-Max-Heap}(A)
\li \For i = \;\textit{length}[A] \;\textbf{downto}\;2
\li \;\;\;\;\textup{exchange}\;A[1]\;\textup{and}\;A[i]
\li \;\;\;\;\textit{heap-size}[A] = \;\textit{heap-size}[A] - 1
\li \;\;\;\;\proc{Max-Heapify}(A, 1)
}@

heapsort 的 running time
BUILD-MAX-HEAP 花費 $O(n)$ 的時間，接著 $n-1$ 次的 MAX-HEAPIFY，總共花費 $O(n \lg n)$ 的時間。