图解说明堆排序堆排序算法和JavaScript代码实现

1.我得谈谈二叉树。要理解堆，首先要理解二叉树。在计算机科学中，二叉树是每个节点最多有两个子树的树结构。一般来说，子树被称为“左子树”和“右子树”。二叉树常用于实现二叉查找树和二进制堆。二叉树的每个节点最多有两个子树(没有大于2度的节点)，二叉树的子树有左右分支，所以顺序不能颠倒。二叉树的I层最多有2i-1个节点；深度为k的二叉树最多有2k-1个节点；对于任意二叉树t，如果终端节点数为n0，2度节点数为n2，则n0=N2 ^ 1。树和二叉树主要有三个区别：树中的节点数至少为1，而二叉树中的节点数可以为0。树的最大节点数没有限制，而二叉树的最大节点数是2。二叉树中的节点分为左节点和右节点。二叉树可以分为完全二叉树和全二叉树：一个深度为k，2k-1。

深度为3的全二叉树：深度为k，节点为n的二叉树，当且仅当每个节点对应深度为k的全二叉树中序号为1到n的节点时，称为全二叉树。

(完全二叉树)深度为3的2)2。什么是堆？一个堆(二进制堆)可以看作是一个完整的二叉树。完整二叉树的“优秀”属性之一是除底层之外的每一层都是满的，这使得堆可以用数组来表示(普通二叉树通常使用链表作为基本容器)，每个节点对应数组中的一个元素。下图显示了堆和数组之间的关系。

(堆与数组的关系)给定一个节点的下标I，很容易计算出这个节点的父节点和子节点的下标：父(i)=floor(i/2)，父节点下标Left(i)=2i，左子节点下标Right(i)=2i 1，右子节点下标I。

二元桩一般分为两种：最大桩和最小桩。最大堆：最大堆中的最大元素值出现在根节点(堆的顶部)。堆中每个父节点的元素值大于或等于其子节点(如果有)。

(最大堆)最小堆：最小堆中的最小元素值出现在根节点(堆的顶部)。在堆中，每个父节点的元素值小于或等于其子节点(如果有)。

(最小堆)3。堆排序原则堆排序是取出最大堆的最大顶数，将剩余的堆调整到最大堆，再取出最大堆的顶数。这个过程一直持续到只剩下一堆。堆中定义了以下操作：Max-heap adjust:调整堆的结束子节点，使子节点始终小于父节点；创建最大堆(构建-最大堆)；对堆中的所有数据重新排序，使其成为最大堆排序；移除第一个数据的根节点，继续最大堆调整的递归操作。

(从零开始)相应的，几个计算公式也要做相应的调整：Parent(i)=floor((i-1)/2)，I的父节点下标Left(i)=2i 1，I的左子节点下标Right(i)=2(i 1)，I的右子节点下标最大堆调整(max \)。

(Max-Heapify)由于堆在一次调整后仍然违反堆属性，所以需要进行递归测试，使整个堆满足堆属性，可以用JavaScript表示如下：

/** * 从指数开始检查并保持最大堆性质* * @数组* * @索引检查的起始下标* * @heapSize堆大小* * */函数maxHeapify(数组、索引、heapSize) { var iMax=index，iLeft=2 * index 1，iRight=2 *(index 1)；if (iLeft heapSize数组[索引]数组[iLeft]){ iMax=iLeft；} if(iRight HeaPsize array[iMaX]array[iRight]){ iMaX=iRight；} if (iMax！=index) { swap(array，iMax，index)；maxHeapify(array，iMax，heapSize)；//递归调整} }函数交换(数组，I，j){ var temp=数组[I]；数组[i]=数组[j]；数组[j]=温度；}通常来说，递归主要用在分治法中，而这里并不需要分治。而且递归调用需要压栈/清栈，和迭代相比，性能上有略微的劣势。当然，按照20/80法则，这是可以忽略的。但是如果你觉得用递归会让自己心里过不去的话，也可以用迭代，比如下面这样：

/** * 从指数开始检查并保持最大堆性质* * @数组* * @索引检查的起始下标* * @heapSize堆大小* * */函数maxHeapify(数组、索引、heapSize) { var iMax、iLeft、iRightwhile(true){ iMax=index；iLeft=2 *索引1;iRight=2 *(索引1);if (iLeft heapSize数组[索引]数组[iLeft]){ iMax=iLeft；} if(iRight HeaPsize array[iMaX]array[iRight]){ iMaX=iRight；} if (iMax！=index) { swap(array，iMax，index)；index=iMax} else { break} } }函数交换(数组，I，j){ var temp=数组[I]；数组[i]=数组[j]；数组[j]=温度；}创建最大堆（构建-最大-堆)的作用是将一个数组改造成一个最大堆，接受数组和堆大小两个参数，构建-最大-堆将自下而上的调用Max-Heapify来改造数组，建立最大堆。因为Max-Heapify能够保证下标我的结点之后结点都满足最大堆的性质，所以自下而上的调用Max-Heapify能够在改造过程中保持这一性质。如果最大堆的数量元素是n，那么构建-最大-堆从父(n)开始，往上依次调用Max-Heapify。流程如下：

用Java脚本语言描述如下：

函数buildMaxHeap(array，heapSize) { var i，iParent=math。楼层((heapSize-1)/2)；for(I=iprent；I=0；i - ) { maxHeapify(array，I，HeaPsize)；}}堆排序（堆排序)是堆排序的接口算法堆排序先调用构建-最大-堆将数组改造为最大堆，然后将堆顶和堆底元素交换，之后将底部上升，最后重新调用Max-Heapify保持最大堆性质。由于堆顶元素必然是堆中最大的元素，所以一次操作之后，堆中存在的最大元素被分离出堆，重复n-1次之后，数组排列完毕。整个流程如下：

用Java脚本语言描述如下：

函数heapSort(数组，heapSize) { buildMaxHeap(数组，heapSize)；for(int I=HeaPsize-1；I 0；i - ) { swap(array，0，I)；maxHeapify(数组，0，I)；} }4.Java脚本语言语言实现最后，把上面的整理为完整的爪哇岛描述语言代码如下：

function Heapsort(array){ function swap(array，I，j){ var temp=array[I]；数组[i]=数组[j]；数组[j]=温度；}函数maxHeapify(数组、索引、heapSize) { var iMax、iLeft、iRightwhile(true){ iMax=index；iLeft=2 *索引1;iRight=2 *(索引1);if (iLeft heapSize数组[索引]数组[iLeft]){ iMax=iLeft；} if(iRight HeaPsize array[iMaX]array[iRight]){ iMaX=iRight；} if (iMax！=index) { swap(array，iMax，index)；index=iMax} else { break} } }函数buildMaxHeap(数组){ var i，iParent=math。地板(阵列。长度/2)-1；for(I=iprent；I=0；i - ) { maxHeapify(array，I，array。长度)；} }函数排序（数组){ buildMaxHeap(数组);for(var I=数组。长度-1；I 0；i - ) { swap(array，0，I)；maxHeapify(数组，0，I)；}返回数组；}返回排序（数组);}5.堆排序算法的运用

(1)算法性能的时间复杂度/复杂度堆排序非常稳定(我们可以看到它对输入数据不敏感)，这就是O(nn)复杂度，最好的情况和最坏的情况是一样的。然而，它的空间复杂性随着不同的实现而变化。也就是说，上面讨论了两个常见的复杂性：O(n)和O(1)。基于节省空间的原则，我推荐O(1)复杂度的方法。

(2)算法稳定性堆排序有大量的筛选和移动过程，是一种不稳定的排序算法。

(3)该算法适用于场景堆排序，在构建和调整堆的过程中会产生相对较大的开销，在元素较少时不适用。但是，当元素很多的时候，还是一个不错的选择。尤其是在解决“前n个大数”这样的问题时，几乎是首选算法。