資料結構--堆排序

    通過學習優先隊列和二叉堆，我們知道優先隊列中隊首的元素總是最大（最大堆）或者最小（最小堆）的元素，根據這個規律，如果我們把一系列無序的元素插入到優先隊列中，然後再從優先隊列中逐個删除元素，則删除元素的順序是有序的。我們由此可以演變得出一種排序算法--堆排序。

    此處以最大堆來讨論，堆排序的實作分為2個階段：構造堆階段和下沉排序階段；

構造堆階段：通過下沉操作，将新添加到堆中的元素放到堆的根節點，然後與較大的子節點比較，如果小于子節點，則與子節點交換位置，使得較小的元素在堆中不斷下沉，放入堆中合适的位置。

下沉排序階段：構造堆完成後，堆的根節點存放的是最大的元素。排序階段，每次将根節點元素與堆數組末尾元素交換位置，然後縮小堆的size，使得最大的元素從堆中剔除，放在數組末尾。然後通過下沉操作，使得根節點的新元素重新下沉到合适的位置。如此往複，直到堆中沒有元素。此時，堆數組中的元素變為升序排列。

首先實作堆排序中需要的3個基本操作：

比較（less）：比較兩個元素的大小，元素需要實作Comparable接口，進而可以被比較；

交換（exch）：交換兩個元素在數組中的位置；

下沉（sink）：通過比較和交換，自上而下的移動元素，使其達到合适的位置；

    排序方法sort實際是對上面3個基本操作的組合，在構造堆階段，通過sink操作構造好二叉堆。在排序階段，通過exch操作将最大的元素排除到堆外，放到數組最末端，然後通過sink操作使堆重新變得有序。如此往複,直至堆中沒有元素，此時數組即是有序的。基于最大堆的堆排序是升序的，反之，基于最小堆的堆排序是降序的。完整代碼如下：

從上面代碼可以看出，堆排序使用待排數組本身作為堆的存儲結構，不占用額外的空間，因而屬于内部排序。

    堆排序的主要工作都是在下沉排序階段完成的，每次從堆中删除最大的元素，然後放入到堆縮小後空出的空間中。這個過程和選擇排序的過程類似，都是選擇最大/最小的元素放到數組末尾，但相比于選擇排序，堆排序在查找最大/最小元素的效率為$O(logN)$，高于選擇排序的$O(N)$，進而提升了排序效率。

<a href="https://algs4.cs.princeton.edu/24pq/?spm=a2c4e.11153940.blogcont574087.13.4a774a58aGFL75">算法（第4版）2.4節-優先隊列</a>

<a href="https://www.coursera.org/learn/algorithms-part1/home/week/4?spm=a2c4e.11153940.blogcont574087.14.4a774a58aGFL75">coursera算法視訊課程</a>

<a href="https://www.toptal.com/developers/sorting-algorithms/heap-sort">堆排序示意動畫</a>