JS实现堆排序

Scorpion 发布于2019-08-22 18:31 / 1742人阅读

摘要：堆的存储堆由数组来实现，相当于对二叉树做层序遍历。实现交换两个节点将结点以下的堆整理为大顶堆，注意这一步实现的基础实际上是假设结点以下的子堆已经是一个大顶堆，函数实现的功能是实际上是找到结点在包括结点的堆中的正确位置。

堆的预备知识

堆是一个完全二叉树。

完全二叉树：二叉树除开最后一层，其他层结点数都达到最大，最后一层的所有结点都集中在左边（左边结点排列满的情况下，右边才能缺失结点）。

大顶堆：根结点为最大值，每个结点的值大于或等于其孩子结点的值。

小顶堆：根结点为最小值，每个结点的值小于或等于其孩子结点的值。

堆的存储：堆由数组来实现，相当于对二叉树做层序遍历。如下图：

对于结点 i ，其子结点为 2i+1 与 2i+2 。

堆排序算法

现在需要对如上二叉树做升序排序，总共分为三步：

将初始二叉树转化为大顶堆（heapify）（实质是从第一个非叶子结点开始，从下至上，从右至左，对每一个非叶子结点做shiftDown操作），此时根结点为最大值，将其与最后一个结点交换。

除开最后一个结点，将其余节点组成的新堆转化为大顶堆（实质上是对根节点做shiftDown操作），此时根结点为次最大值，将其与最后一个结点交换。

重复步骤2，直到堆中元素个数为1（或其对应数组的长度为1），排序完成。

下面详细图解这个过程：

步骤1：

初始化大顶堆，首先选取最后一个非叶子结点(我们只需要调整父节点和孩子节点之间的大小关系，叶子结点之间的大小关系无需调整)。设数组为arr，则第一个非叶子结点的下标为：i = Math.floor(arr.length/2 - 1) = 1，也就是数字4，如图中虚线框，找到三个数字的最大值，与父节点交换。

然后，下标 i 依次减1（即从第一个非叶子结点开始，从右至左，从下至上遍历所有非叶子节点）。后面的每一次调整都是如此：找到父子结点中的最大值，做交换。

这一步中数字6、1交换后，数字[1,5,4]组成的堆顺序不对，需要执行一步调整。因此需要注意，每一次对一个非叶子结点做调整后，都要观察是否会影响子堆顺序！

这次调整后，根节点为最大值，形成了一个大顶堆，将根节点与最后一个结点交换。

步骤2：

除开当前最后一个结点6(即最大值)，将其余结点[4,5,3,1]组成新堆转化为大顶堆(注意观察，此时根节点以外的其他结点，都满足大顶堆的特征，所以可以从根节点4开始调整，即找到4应该处于的位置即可)。

步骤3：

接下来反复执行步骤2，直到堆中元素个数为1：

堆中元素个数为1，排序完成。

JavaScript实现

// 交换两个节点
function swap(A, i, j) {
  let temp = A[i];
  A[i] = A[j];
  A[j] = temp; 
}

// 将 i 结点以下的堆整理为大顶堆，注意这一步实现的基础实际上是：
// 假设 结点 i 以下的子堆已经是一个大顶堆，shiftDown函数实现的
// 功能是实际上是：找到 结点 i 在包括结点 i 的堆中的正确位置。后面
// 将写一个 for 循环，从第一个非叶子结点开始，对每一个非叶子结点
// 都执行 shiftDown操作，所以就满足了结点 i 以下的子堆已经是一大
//顶堆
function shiftDown(A, i, length) {
  let temp = A[i]; // 当前父节点
// j=0; i--) {
    shiftDown(A, i, A.length);
  }
  // 排序，每一次for循环找出一个当前最大值，数组长度减一
  for(let i = Math.floor(A.length-1); i>0; i--) {
    swap(A, 0, i); // 根节点与最后一个节点交换
    shiftDown(A, 0, i); // 从根节点开始调整，并且最后一个结点已经为当
                         // 前最大值，不需要再参与比较，所以第三个参数
                         // 为 i，即比较到最后一个结点前一个即可
  }
}

let Arr = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2];
heapSort(Arr);
alert(Arr);

程序注释：将 i 结点以下的堆整理为大顶堆，注意这一步实现的基础实际上是：假设结点 i 以下的子堆已经是一个大顶堆，shiftDown函数实现的功能是实际上是：找到结点 i 在包括结点 i 的堆中的正确位置。后面做第一次堆化时，heapSort 中写了一个 for 循环，从第一个非叶子结点开始，对每一个非叶子结点都执行 shiftDown操作，所以就满足了每一次 shiftDown中，结点 i 以下的子堆已经是一大顶堆。

复杂度分析：adjustHeap 函数中相当于堆的每一层只遍历一个结点，因为
具有n个结点的完全二叉树的深度为[log2n]+1，所以 shiftDown的复杂度为 O(logn)，而外层循环共有 f(n) 次，所以最终的复杂度为 O(nlogn)。

堆的应用

堆主要是用来实现优先队列，下面是优先队列的应用示例：

操作系统动态选择优先级最高的任务执行。

静态问题中，在N个元素中选出前M名，使用排序的复杂度：O(NlogN)，使用优先队列的复杂度: O(NlogM)。

而实现优先队列采用普通数组、顺序数组和堆的不同复杂度如下：

使用堆来实现优先队列，可以使入队和出队的复杂度都很低。

超融合服务器 idc机房托管堆排序堆排序算法堆排序排序c语言 js实现table排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/95953.html

JavaScript 数据结构与算法之美 - 归并排序、快速排序、希尔排序、堆排序

摘要：之所以把归并排序快速排序希尔排序堆排序放在一起比较，是因为它们的平均时间复杂度都为。归并排序是一种稳定的排序方法。因此，快速排序并不稳定。希尔排序思想先将整个待排序的记录序列分割成为若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言算法为王。想学好前端，先练好内功，只有内功深厚者，前端之路才...

haitiancoder 2019-08-26 10:20 评论0 收藏0
排序算法速度测试（插入排序、二分法插入、选择排序、快速排序、堆排序）js实现

摘要：公共函数库用于取出随机排列的数字原数组给原数组赋值排序算法插入排序时间复杂度二分法插入排序选择排序快速排序一堆排序测试用例插入排序时间测试二分法插入排序时间测试选择排序时间测试快速排序时间测试一堆公共函数库（用于取出随机排列的数字） module.exports={ randomIntegerArray:function(count){ var origina...

mochixuan 2019-08-20 16:04 评论0 收藏0
堆排序 js实现

摘要：堆排序实现最近在看语言版的数据结构，用法着实很难，于是按照意思，仿照语言写了版的三种排序方法仅供大家一起学习和参考后续比较难的归并排序，和快速排序，以后再说，废话不说，直接边代码边讲解希尔排序，将表分为几段长度，分别进行排序，然后进行总的排堆排序 js实现 /* 最近在看c语言版的数据结构，c用法着实很难，于是按照意思，仿照c语言写了javascript版的三种排序方法！仅供大家一...

elva 2019-08-20 16:05 评论0 收藏0
js实现堆排序

摘要：堆排序构造大顶堆第一个元素就是最大的，然后跟最后一个元素交换，把最大的弹出栈第一个元素与它的左右子节点比较，左右子节点中较大的比它大则交换然后再递归地这样交换下去直到没有比它大的子节点或者没有子节点。堆排序构造大顶堆第一个元素就是最大的，然后跟最后一个元素交换，把最大的弹出栈第一个元素与它的左右子节点比较，左右子节点中较大的比它大则交换然后再递归地这样交换下去直到没有比它大的子节...

big_cat 2019-08-20 15:16 评论0 收藏0
基于 Javascript 排序算法

摘要：适用于数据比较少或基本有序的情况。插入排序时间复杂度为，空间复杂度为，属于稳定排序。算法适用于少量数据的排序。就像下图这样，可以理解桶的意思下图是整个排序过程示意图基数排序时间复杂度为，空间复杂度为，属于稳定排序。写在前面个人感觉：javascript对类似排序查找这样的功能已经有了很好的封装，以致于当我们想对数组排序的时候只需要调用arr.sort()方法，而查找数组元素也只需要...

tommego 2019-08-23 11:47 评论0 收藏0