位置: 编程技术 - 正文
图文详解Heap Sort堆排序算法及JavaScript的代码实现(图文详解地理图册电子版)
编辑：rootadmin推荐整理分享图文详解Heap Sort堆排序算法及JavaScript的代码实现(图文详解地理图册电子版)，希望有所帮助，仅作参考，欢迎阅读内容。
文章相关热门搜索词:图文详解管道支架制作安装标准,图文详解:台盆柜安装的全过程,图文详解历史图册,图文详解地理图册电子版,图文详解管道支架制作安装标准,图文详解地理图册电子版,图文详解地理图册,图文详解管道支架制作安装标准,内容如对您有帮助，希望把文章链接给更多的朋友！
1. 不得不说说二叉树要了解堆首先得了解一下二叉树，在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。二叉树的每个结点至多只有二棵子树（不存在度大于 2 的结点），二叉树的子树有左右之分，次序不能颠倒。二叉树的第 i 层至多有 2i - 1 个结点；深度为 k 的二叉树至多有 2k - 1 个结点；对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点数为 n2，则n0 = n2 + 1。树和二叉树的三个主要差别：树的结点个数至少为 1，而二叉树的结点个数可以为 0树中结点的最大度数没有限制，而二叉树结点的最大度数为 2树的结点无左、右之分，而二叉树的结点有左、右之分二叉树又分为完全二叉树（complete binary tree）和满二叉树（full binary tree）满二叉树：一棵深度为 k，且有 2k - 1 个节点称之为满二叉树
（深度为 3 的满二叉树 full binary tree）完全二叉树：深度为 k，有 n 个节点的二叉树，当且仅当其每一个节点都与深度为 k 的满二叉树中序号为 1 至 n 的节点对应时，称之为完全二叉树
（深度为 3 的完全二叉树 complete binary tree）2. 什么是堆？堆（二叉堆）可以视为一棵完全的二叉树，完全二叉树的一个“优秀”的性质是，除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示（普通的一般的二叉树通常用链表作为基本容器表示），每一个结点对应数组中的一个元素。如下图，是一个堆和数组的相互关系
（堆和数组的相互关系）对于给定的某个结点的下标 i，可以很容易的计算出这个结点的父结点、孩子结点的下标：Parent(i) = floor(i/2)，i 的父节点下标Left(i) = 2i，i 的左子节点下标Right(i) = 2i + 1，i 的右子节点下标
二叉堆一般分为两种：最大堆和最小堆。最大堆：最大堆中的最大元素值出现在根结点（堆顶）堆中每个父节点的元素值都大于等于其孩子结点（如果存在）
（最大堆）最小堆：最小堆中的最小元素值出现在根结点（堆顶）堆中每个父节点的元素值都小于等于其孩子结点（如果存在）
（最小堆）3. 堆排序原理堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算继续进行下面的讨论前，需要注意的一个问题是：数组都是 Zero-Based，这就意味着我们的堆数据结构模型要发生改变
（Zero-Based）相应的，几个计算公式也要作出相应调整：Parent(i) = floor((i-1)/2)，i 的父节点下标Left(i) = 2i + 1，i 的左子节点下标Right(i) = 2(i + 1)，i 的右子节点下标最大堆调整（MAX?HEAPIFY）的作用是保持最大堆的性质，是创建最大堆的核心子程序，作用过程如图所示：
（Max-Heapify）由于一次调整后，堆仍然违反堆性质，所以需要递归的测试，使得整个堆都满足堆性质，用 JavaScript 可以表示如下：
通常来说，递归主要用在分治法中，而这里并不需要分治。而且递归调用需要压栈/清栈，和迭代相比，性能上有略微的劣势。当然，按照/法则，这是可以忽略的。但是如果你觉得用递归会让自己心里过不去的话，也可以用迭代，比如下面这样：
创建最大堆（Build-Max-Heap）的作用是将一个数组改造成一个最大堆，接受数组和堆大小两个参数，Build-Max-Heap 将自下而上的调用 Max-Heapify 来改造数组，建立最大堆。因为 Max-Heapify 能够保证下标 i 的结点之后结点都满足最大堆的性质，所以自下而上的调用 Max-Heapify 能够在改造过程中保持这一性质。如果最大堆的数量元素是 n，那么 Build-Max-Heap 从 Parent(n) 开始，往上依次调用 Max-Heapify。流程如下：
用 JavaScript 描述如下：
堆排序（Heap-Sort）是堆排序的接口算法，Heap-Sort先调用Build-Max-Heap将数组改造为最大堆，然后将堆顶和堆底元素交换，之后将底部上升，最后重新调用Max-Heapify保持最大堆性质。由于堆顶元素必然是堆中最大的元素，所以一次操作之后，堆中存在的最大元素被分离出堆，重复n-1次之后，数组排列完毕。整个流程如下：
用 JavaScript 描述如下：
4.JavaScript 语言实现最后，把上面的整理为完整的 javascript 代码如下：
5.堆排序算法的运用
（1）算法性能/复杂度堆排序的时间复杂度非常稳定（我们可以看到，对输入数据不敏感），为O(n?n)复杂度，最好情况与最坏情况一样。但是，其空间复杂度依实现不同而不同。上面即讨论了两种常见的复杂度：O(n)与O(1)。本着节约空间的原则，我推荐O(1)复杂度的方法。
（2）算法稳定性堆排序存在大量的筛选和移动过程，属于不稳定的排序算法。
（3）算法适用场景堆排序在建立堆和调整堆的过程中会产生比较大的开销，在元素少的时候并不适用。但是，在元素比较多的情况下，还是不错的一个选择。尤其是在解决诸如“前n大的数”一类问题时，几乎是首选算法。
5个最顶级jQuery图表类库插件【jquery插件库】 GraphUpjQueryplugin-美元Graphup是一中非常轻量级的灵活的jQuery(v1.4+)插件用来美化你的数据表。它能够使用颜色，柱状图及其气饱来有效的展现你的数据。
详解JavaScript中基于原型prototype的继承特性 JavaScript中的继承比较奇葩，无法实现接口继承，只能依靠原型继承。原型链原型就是一个对象，通过构造函数创建出来的实例会有指针指向原型得到原
jQuery Mobile 和 Kendo UI 的比较 jQueryMobile和KendoUI都是流行的JavaScript框架，在开发中我们可以在它们的基础上添砖加瓦制作所有现代移动WEB应用。这两个框架都是基于使用率顶尖的JavaSc
标签: 图文详解地理图册电子版
本文链接地址:https://www.jiuchutong.com/biancheng/370023.html 转载请保留说明！
