Data Structures Algorithms 简明教程
Heap Sort Algorithm
堆排序是一种基于 * heap data structure* 的高效排序技术。
堆是一种近乎完整的二叉树，其中父节点可能是最小或最大值。具有最小根节点的堆称为 min-heap ，而具有最大根节点的根节点称为 max-heap 。堆排序算法的输入数据中的元素使用这两种方法进行处理。
堆排序算法在此过程中遵循两个主要操作 −
-
使用 heapify （在本章中进一步解释）方法基于排序方式（升序或降序）从输入数据构建堆 H。
-
删除根元素的根元素并重复此过程，直到处理所有输入元素。
堆排序算法极大地依赖于二叉树的堆化方法。那么，什么是这种堆化方法呢？
Heapify Method
二叉树的堆化方法是将树转换为堆数据结构。此方法使用递归方法堆化二叉树的所有节点。
Note − 二叉树必须始终是完全二叉树，因为它必须始终有两个子节点。
通过应用堆化方法，完整的二叉树将转换为最大堆或最小堆。
要了解更多有关堆化算法的信息，请 click here.
Heap Sort Algorithm
正如在下面的算法中所述，排序算法首先通过调用 Build-Max-Heap 算法构造堆 ADT，并移除根元素以将其与叶子中的最小值节点交换。然后应用堆化方法来相应地重新排列元素。
Algorithm: Heapsort(A)
BUILD-MAX-HEAP(A)
for i = A.length downto 2
exchange A[1] with A[i]
A.heap-size = A.heap-size - 1
MAX-HEAPIFY(A, 1)Analysis
堆排序算法是插入排序和归并排序这两种其他排序算法的结合。
它与插入排序的相似之处包括，任何时候仅在输入数组外部存储一个恒定的数组元素数量。
堆排序算法的时间复杂度为 O(nlogn) ，类似于归并排序。
The Heapify Algorithm
应用堆化方法，从堆中移除根节点，并将其替换为根的下一个立即最大值的孩子。
根节点为 23，因此弹出 23，并将 18 设置为下一个根，因为它是在堆中的下一个最大节点。
现在，弹出 18 后 23 被 14 替换。
弹出当前根 14，并将其替换为 12。
弹出 12 并用 10 替换。
同样，使用相同方法弹出所有其他元素。
在此，弹出当前根元素 9，并且元素 8 和 3 保留于树中。
然后，将弹出 8 留下 3 在树中。
在给定堆中完成堆排序操作后，排序元素将按如下所示显示——
每次弹出元素时，都会将其添加到输出数组的开头，因为形成的堆数据结构是一个大顶堆。但是，如果堆化方法将二叉树转换为小顶堆，则将弹出元素添加到输出数组的末尾。
最终的排序列表是，