這章節來介紹Heap Sort。

首先把array轉換成max-heap：

再來把max-heap最大的元素放到我們新建的output array：

拿掉後max-heap會進行sink的動作重組出剩下元素該有的max-heap，之後不斷循環這個步驟。

最後的output array就是結果：

總結一下剛剛的heap sort方法，在時間效率上很不錯，不過空間效率表現不出色，但也不會是很嚴重的問題：

有沒有可能改善空間效率呢？有的，就是直接使用原來的array進行heapify跟重組：

我們從最尾端開始進行sink，不斷進行就可以慢慢將整個array變成max-heap：

以上就完成了heapify。接下來sort的動作也不必創建新的output array來存！直接原地進行，因為sort好的元素就會被放在最旁邊，只要把剩下的元素在進行重新heapify就好了：

一樣的步驟省略，最後完成如下：

搞定！下面總結一下這個版本的heap sort，空間效率大幅提升！

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License