JS算法:图文并茂讲解堆排序

语言: CN / TW / HK

前言

文中用 JavaScript 实现算法,详细解释堆排序 js 中堆的创建与维护,以及堆排序算法的实现堆创建。

理论

堆,是具有下列性质的完全二叉树:每个节点的值都小于等于其左右孩子节点值是小根堆;(大于等于则是大根堆)。批注:有些参考书将堆直接定义为序列,但是,从逻辑结构上讲,还是将堆定义为完全二叉树更好。虽然堆的典型实现方法是数组,但从逻辑的角度上讲,堆实际上是一种树结构。

对于数组实现的堆,是一个完全二叉树,其中任意一个节点 i 都满足以下公式

  • Parent(i) = floor((i-1)/2),i 的父节点下标
  • Left(i) = 2i + 1,i 的左子节点下标
  • Right(i) = 2(i + 1),i 的右子节点下标

思路

  • 此思路用于将任意数组调整成大根堆
  • 首先将数组想象成是一个完美二叉树
  • 我们的目的是将这个二叉数调整成大根堆,即每个节点的值都大于等于其左右孩子节点值
  • 首先,寻找到最后一个根节点,此根节点有一个孩子是数组的最后一个元素
  • 然后找出大的孩子节点与根节点对比,如果大的孩子节点比根节点大,则将根节点与大的孩子节点互换,保证根节点最大
  • 接着向前遍历根节点
  • 对每个根节点,都首先找出比较大的孩子节点,然后将大的孩子节点与根节点对比
  • 如果孩子节点比根节点大,那么将孩子节点与根节点互换
  • 然后将互换后得到新值的孩子节点作为新的根节点,将其与它自己的子节点再重复以上对比,以此进行深度遍历的重复操作,直到此相关树上的根节点都比孩子节点大为止
  • 深度遍历操作完后,继续执行前面的根节点遍历操作,直到遍历到最后一个根节点

例子

  • 现有数组 arr = [5,8,3,5,2,99,22,44],将其调整为大根堆
  • 数组可以表示堆即完美二叉树,因此将其转化成完美二叉树理解(此处可自行搜索,完美二叉树用数组表示),如下图所示
0.png
  • 寻找最后一个根节点,用 i 表示,从 arr.length / 2 作为初始值向前查找
  • 当 i = arr.length / 2 = 4 时没有孩子节点,所以它不是根节点
  • 向前遍历节点,当 i = 3 时,它拥有孩子节点 arr[arr.length - 1],所以 arr[3] = 5 就是我们想找的最后一个根节点
  • 此时我们可以得最后一颗子树,如下图标记所示
图1.png
  • 然后我们针对这颗子树进行调整操作


    • 找到最大的孩子节点,用 child 表示,此时只有一个孩子节点 arr.length - 1,所以 child = arr.length - 1 = 7
    • 将 child 与根节点(i = 3)对比,如果 child 的值 i 的值大,则互换值
    • 此处 child 比 i 的值大所以互换值,child 的值改为 5,i 的值改为 44
    • 由于 child 没有孩子节点所以不进行更深层次的遍历
  • 操作完之后如下图所示

2.png
  • 然后向前继续寻找根节点,当 i = 2 的时候,我们将找到一颗新的子树
3.png
  • 对这颗找到的树进行调整操作


    • 寻找大的孩子节点,用 child 表示,由图可知最大的孩子节点的值为 99,所以 child = 5
    • 当前的根节点 i = 2,由于 child 的值比 i 的值大,所以互换
    • 同时由于 child 后面没有孩子节点,所以结束操作
  • 上面操作后可得到下图所示的树

4.png
  • 继续向前寻找根节点,当 i = 1 的时候,我们找到一颗新的树
5.png
  • 对这颗树进行调整操作,此时 i = 1,child = 3


    • 按照上面步骤,首先互换 child 和 i 的值
6.png

    • 然后由于 child 有孩子节点,所以将 i 指向 i,将 child 指向它自己的孩子节点
    • 得到 i = 3, child = 7 重复比较操作,如果孩子节点比根节点大互换值
    • 此处 arr[i] = 8,arr[child] = 5 根节点比孩子节点大,所以不替换
  • 最终得到的树如下图所示
6.png
  • 继续向前遍历,得到最后一颗新树,根节点为 i = 0
7.png
  • 对这颗树进行调整操作


    • 此时 i = 0
    • 先寻找 child = 2,arr[child] = 99
    • arr[child] = 99 > arr[i] = 5,互换得到 arr[child] = 5,arr[i] = 99
8.png

    • 由于 child 有孩子节点,所以对 child 的孩子节点进行深度调整
    • i = child = 2,child = 2 * i + 1 = 5
    • 由于此时有左右两个孩子节点,索引分别为 5 和 6,并且索引为 6 的节点值比较大,所以 child 更改为 6
    • 比较 i 与 child 的值
    • arr[i] = arr[2] = 5 小于 arr[child] = arr[6] = 22
    • 所以进行值互换,得到 arr[i] = 22,arr[child] = 5
9.png

    • 此时 child 没有孩子节点,停止深度调整
  • 最终得到大根堆如下图所示
9.png
  • 用数组进行表示则为:[99, 44, 22, 8, 2, 3, 5, 5]

代码

/**
 *  此代码建议 mock 数据,并将其绘制成完美二叉树,参照二叉树进行阅读
 */
function buildHeap(data){
    let len = data.length
        // 从最后一个根节点开始,向前遍历所有根节点
    // 取 len / 2 作为 i 的初始值,是因为最后一个孩子节点是 len - 1
    // 它可能是左孩子也可能是右孩子,那么可以根据公式算出对应的根节点
    // 它一定在 len / 2 附近,且小于 len / 2
    for(let i = Math.floor(len / 2); i >= 0; i --){
       heapAjust(data, i, len);
    }
}

/**
 * 调整操作
 * 根据传入的数据调整二叉树
 * i 为根节点的 key
 * len 为需调整数据的长度
 */
function heapAjust(data, i, len){
    // 寻找 i 的左孩子
    let child = 2 * i + 1
        // 如果 child 大于 len 说明 i 不是根节点
    while(child < len) {
                // 比较两个孩子节点,将 child 指向大的那个
        if(child + 1 <= len && data[child] < data[child + 1]){
            child = child + 1
        }
        // 如果孩子节点比根节点大,两个节点互换
        if(data[i] < data[child]){
                        let temp = data[i]
            data[i] = data[child]
            data[child] = temp 
            // 互换之后将被更新的孩子节点继续作为根节点,进行深度查找
            i = child
            child = 2 * i + 1
        }
        else {
            break
        }
    }
}

堆排序

思路

  • 先将整个数组调整成大根堆
  • 则数组的第一个元素最大,将其与数组最后一个元素替换,此时大根堆被破坏
  • 重新调整前 length - 1 个元素,将它们调整成新的大根堆
  • 以此循环,直到堆中的元素只有一个时

代码

var arraySort = function(arr) {
    // 将数组调整成大根堆
    buildHeap(arr);
    // 下面需要注意的时候参数的边界
    for(let i = arr.length - 1; i >= 0; i --) {
        // 互换数据
            let temp = arr[i]
        arr[i] = arr[0]
        arr[0] = temp 
                // 将前面的元素重新调整成大根堆
        heapAjust(arr, 0, i-1);
    }
}

总结

  • 堆排序是不稳定的
  • 在寻找前几个值最大的场景中比较好用

源自:https://juejin.cn/post/6932718585173753869

声明:文章著作权归作者所有,如有侵权,请联系小编删除。

感谢 · 转发欢迎大家留言

本文分享自微信公众号 - web前端学习圈(web-xxq)。
如有侵权,请联系 [email protected] 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

分享到: