Data Structures Algorithms 简明教程

Heap Sort Algorithm

堆排序是一种基于 * heap data structure* 的高效排序技术。

Heap Sort is an efficient sorting technique based on the heap data structure.

堆是一种近乎完整的二叉树，其中父节点可能是最小或最大值。具有最小根节点的堆称为 min-heap ，而具有最大根节点的根节点称为 max-heap 。堆排序算法的输入数据中的元素使用这两种方法进行处理。

The heap is a nearly-complete binary tree where the parent node could either be minimum or maximum. The heap with minimum root node is called min-heap and the root node with maximum root node is called max-heap. The elements in the input data of the heap sort algorithm are processed using these two methods.

堆排序算法在此过程中遵循两个主要操作 −

The heap sort algorithm follows two main operations in this procedure −

Builds a heap H from the input data using the heapify (explained further into the chapter) method, based on the way of sorting – ascending order or descending order.
Deletes the root element of the root element and repeats until all the input elements are processed.

堆排序算法极大地依赖于二叉树的堆化方法。那么，什么是这种堆化方法呢？

The heap sort algorithm heavily depends upon the heapify method of the binary tree. So what is this heapify method?

Heapify Method

二叉树的堆化方法是将树转换为堆数据结构。此方法使用递归方法堆化二叉树的所有节点。

The heapify method of a binary tree is to convert the tree into a heap data structure. This method uses recursion approach to heapify all the nodes of the binary tree.

Note − 二叉树必须始终是完全二叉树，因为它必须始终有两个子节点。

Note − The binary tree must always be a complete binary tree as it must have two children nodes always.

通过应用堆化方法，完整的二叉树将转换为最大堆或最小堆。

The complete binary tree will be converted into either a max-heap or a min-heap by applying the heapify method.

要了解更多有关堆化算法的信息，请 click here.

To know more about the heapify algorithm, please click here.

Heap Sort Algorithm

正如在下面的算法中所述，排序算法首先通过调用 Build-Max-Heap 算法构造堆 ADT，并移除根元素以将其与叶子中的最小值节点交换。然后应用堆化方法来相应地重新排列元素。

As described in the algorithm below, the sorting algorithm first constructs the heap ADT by calling the Build-Max-Heap algorithm and removes the root element to swap it with the minimum valued node at the leaf. Then the heapify method is applied to rearrange the elements accordingly.

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

堆排序算法是插入排序和归并排序这两种其他排序算法的结合。

The heap sort algorithm is the combination of two other sorting algorithms: insertion sort and merge sort.

它与插入排序的相似之处包括，任何时候仅在输入数组外部存储一个恒定的数组元素数量。

The similarities with insertion sort include that only a constant number of array elements are stored outside the input array at any time.

堆排序算法的时间复杂度为 O(nlogn) ，类似于归并排序。

The time complexity of the heap sort algorithm is O(nlogn), similar to merge sort.

Example

让我们看一个示例数组，以便更好地理解排序算法——

Let us look at an example array to understand the sort algorithm better −

使用来自输入数组的 BUILD-MAX-HEAP 算法构建堆——

Building a heap using the BUILD-MAX-HEAP algorithm from the input array −

通过交换节点来重新排列获得的二叉树，以便形成堆数据结构。

Rearrange the obtained binary tree by exchanging the nodes such that a heap data structure is formed.

The Heapify Algorithm

应用堆化方法，从堆中移除根节点，并将其替换为根的下一个立即最大值的孩子。

Applying the heapify method, remove the root node from the heap and replace it with the next immediate maximum valued child of the root.

根节点为 23，因此弹出 23，并将 18 设置为下一个根，因为它是在堆中的下一个最大节点。

The root node is 23, so 23 is popped and 18 is made the next root because it is the next maximum node in the heap.

现在，弹出 18 后 23 被 14 替换。

Now, 18 is popped after 23 which is replaced by 14.

弹出当前根 14，并将其替换为 12。

The current root 14 is popped from the heap and is replaced by 12.

弹出 12 并用 10 替换。

12 is popped and replaced with 10.

同样，使用相同方法弹出所有其他元素。

Similarly all the other elements are popped using the same process.

在此，弹出当前根元素 9，并且元素 8 和 3 保留于树中。

Here the current root element 9 is popped and the elements 8 and 3 are remained in the tree.

然后，将弹出 8 留下 3 在树中。

Then, 8 will be popped leaving 3 in the tree.

在给定堆中完成堆排序操作后，排序元素将按如下所示显示——

After completing the heap sort operation on the given heap, the sorted elements are displayed as shown below −

每次弹出元素时，都会将其添加到输出数组的开头，因为形成的堆数据结构是一个大顶堆。但是，如果堆化方法将二叉树转换为小顶堆，则将弹出元素添加到输出数组的末尾。

Every time an element is popped, it is added at the beginning of the output array since the heap data structure formed is a max-heap. But if the heapify method converts the binary tree to the min-heap, add the popped elements are on the end of the output array.

最终的排序列表是，

The final sorted list is,

Implementation

应用于堆排序实现的逻辑是：首先，根据大顶堆属性构建堆数据结构，其中父节点的值必须大于子节点的值。然后从堆中弹出根节点，并将堆上的下一个最大节点移至根。此过程会不断迭代，直到堆为空。

The logic applied on the implementation of the heap sort is: firstly, the heap data structure is built based on the max-heap property where the parent nodes must have greater values than the child nodes. Then the root node is popped from the heap and the next maximum node on the heap is shifted to the root. The process is continued iteratively until the heap is empty.

在本教程中，我们将展示四种不同编程语言中的堆排序实现。

In this tutorial, we show the heap sort implementation in four different programming languages.