[深入21] 数据结构和算法 - 二分查找和排序

2021-10-01  本文已影响0人  woow_wu7

导航

[react] Hooks

[React 从零实践01-后台] 代码分割
[React 从零实践02-后台] 权限控制
[React 从零实践03-后台] 自定义hooks
[React 从零实践04-后台] docker-compose 部署react+egg+nginx+mysql
[React 从零实践05-后台] Gitlab-CI使用Docker自动化部署

[源码-webpack01-前置知识] AST抽象语法树
[源码-webpack02-前置知识] Tapable
[源码-webpack03] 手写webpack - compiler简单编译流程
[源码] Redux React-Redux01
[源码] axios
[源码] vuex
[源码-vue01] data响应式 和 初始化渲染
[源码-vue02] computed 响应式 - 初始化，访问，更新过程
[源码-vue03] watch 侦听属性 - 初始化和更新
[源码-vue04] Vue.set 和 vm.$set
[源码-vue05] Vue.extend

[源码-vue06] Vue.nextTick 和 vm.$nextTick
[部署01] Nginx
[部署02] Docker 部署vue项目
[部署03] gitlab-CI

[数据结构和算法01] 二分查找和排序

[深入01] 执行上下文
[深入02] 原型链
[深入03] 继承
[深入04] 事件循环
[深入05] 柯里化 偏函数 函数记忆
[深入06] 隐式转换 和 运算符
[深入07] 浏览器缓存机制（http缓存机制）
[深入08] 前端安全
[深入09] 深浅拷贝
[深入10] Debounce Throttle
[深入11] 前端路由
[深入12] 前端模块化
[深入13] 观察者模式 发布订阅模式 双向数据绑定
[深入14] canvas
[深入15] webSocket
[深入16] webpack
[深入17] http 和 https
[深入18] CSS-interview
[深入19] 手写Promise
[深入20] 手写函数
[深入21] 数据结构和算法 - 二分查找和排序

(一) 前置知识

(1) 一些单词

binary：一半
closure：闭包
recursive：递归

heap 堆
stack 栈
square root 平方根
round：四舍五入
radix：基数
bubbling：冒泡
pivot：支点，基准点

(2) Math

Math.max(1, 2, 3.33, 3) // 3.33 最大值
Math.min(11, 33, 4.44, 22) // 4.44 最小值
Math.min() // Infinity
Math.max() // -Infinity

Math.floor(3.7) // 3 向下取整
Math.ceil(3.1) // 4 向上取整

Math.round(0.1) // 0 四舍五入
Math.round(0.5) // 1 四舍五入

Math.round(-1.1) // -1 四舍五入对负数的处理，主要注意 .5 的情况
Math.round(-1.5) // -1
Math.round(-1.6) // -2

var radius = 20;
var area = Math.PI * Math.pow(radius, 2); // 圆的面积计算

(3) parseInt

一道面试题

['1', '2', '3'].map(parseInt)
相当于
['1', '2', '3'].map((value, index, arr) => parseInt(value, index))
相当于
parseInt('1', 0) => 1 , 当radix是0时，radix会被当成10进制来处理
parseInt('2', 1) => NaN , 1进制不可能有2
parseInt('3', 2) => NaN ，2进制不可能有3，最大是2
最终结果
[1, NaN, NaN]

--------------

[1, 2, 3].map(Number)
相当于
['1', '2', '3'].map((value, index, arr) => Number(value))
最终
[1, 2, 3]

(4) break，continue，return

(5) 时间复杂度

(二) 二分查找

二分法查找 - 非递归方法

(1) 非递归算法
const arr = [1, 2, 3, 4, 5, 6, 7, 8]
function binary_search(arr, value) {
  let low = 0
  let high = arr.length
  while (low <= high) {
    const mid = Math.floor((low + high) / 2)
    // - 1. 注意：这里用 Math.floor 或者 Math.ceil 或者 parseInt 都没有影响
    //           因为条件不成立时，都会跳到对应的一半的部分继续寻找
    // - 2. parseInt() 当有小数点的时候，会取整数，舍弃掉小数部分
    // - 3. ( low + hight / 2  ) 就是中间的位置，当集合是连续的数字时，这里是数组的下标，是连续的，数组永远成立
    if (low === high && arr[mid] !== value) {
      return -1 // 当low和hight相等，arr[mid]还不等于value，说明value在数组中不存在，返回-1
    }
    switch (true) { // 这里非常讨巧的适用了 switch(true) 来代替 if 语句
      case arr[mid] === value:
        return mid // 结束掉整个函数，即binary_search， 并且返回mid的值
      case arr[mid] > value:
        high = mid - 1 // 数组中间值大于value，则在前一半的数组中查找，其实这里也可以不减去1，直接 hight = mid
        break
      case arr[mid] < value:
        low = mid + 1 // 后一半查找
        break
      default:
        return -1 // 没找到
    }
  }
}
const res = binary_search(arr, 5)
console.log(res) // 4

二分法查找 - 递归方法1

(2) 递归方法1
const arr = [1, 2, 3, 4, 5, 6, 7, 8]
function binary_search(arr, value) {
  let low = 0
  let high = arr.length

  function closureAndRecursive(value) { // 利用闭包和递归，low和high即可记住上次的值，相当于全局变量，其实类似于作用域
    const mid = Math.floor((low + high) / 2) // 每次重新计算mid，因为low或者high改变了

    if (low >= high && arr[mid] !== value) return -1; // 递归结束的条件1

    switch (true) {
      case arr[mid] === value:
        return mid // 递归结束的条件2
      case arr[mid] > value:
        high = mid - 1
        return closureAndRecursive(value) // 改变high后继续判断
      case arr[mid] < value:
        low = mid + 1
        return closureAndRecursive(value) // 改变low后继续判断
    }
  }

  return closureAndRecursive(value)
}
const res = binary_search(arr, 5)
console.log(res)

二分法查找 - 递归方法2

(3) 递归方法2
// 通过参数改变low和heigh
const arr = [1, 2, 3, 4, 5, 6, 7, 8]
function binary_search_recursive (arr, value, low, heigh) {
  if (low > heigh) {
    return -1 // 递归结束条件
  }
  const mid = Math.floor((low + heigh) / 2)

  if (arr[mid] === value) {
    return mid
  }
  if (arr[mid] < value) {
    low = mid + 1
    return binary_search_recursive(arr, value, low, heigh)
  }
  if (arr[mid] > value) {
    heigh = mid - 1
    return binary_search_recursive(arr, value, low, heigh)
  }
}
const res = binary_search_recursive(arr, 5, 0, arr.length - 1)
console.log(res)
image

(三) 排序

image
[图片上传失败...(image-856307-1633065665055)]

(1) 冒泡排序 ( bubble-sort )

第一版 - 冒泡排序

冒泡排序 （bubble-sort）

1. 趟数 和 每一趟比较的次数
  - 总趟数 = 数组长度 - 1
  - 每一趟比较的次数 = 总趟数 - 当前趟数
    // 注意，之所以减去趟数，是因为第一趟确定了一个最大值，第二次确定了第二大的值，不需要再做无畏的比较
2. 
第一趟比较完：即得出最大值，且冒泡到数组末尾 ------------------------------------ 执行次数：数组长度 - 当前趟数
第二趟比较完：即得出第二大的值，且冒泡到数组倒数第二个位置，依次类推 -------------- 执行次数：数组长度 - 当前趟数


3. 代码
const arr = [1, 4, 3, 2]
function bubble_sort(arr) {
  const len = arr.length - 1
  for (let i = 0; i < len; i++) { // ------------------- 总趟数 = 数组长度 - 1
    for (let j = 0; j < len - i; j++) { // ------------- 每趟比较的次数 = 总趟数 - 当前趟数
      if (arr[j] > arr[j + 1]) { // -------------------- 两两比较，前者大于后者，大的冒泡到后面
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]] // - 交换位置
      }
    }
  }
  return arr // 返回排好序的数组
}
const orderedArr = bubble_sort(arr)
console.log('orderedArr', orderedArr)

第二版 - 冒泡排序

第二版
1. 可以优化的点
  - 每趟的次数
    - 最原始：每趟比较 length -1 次
    - 第一版：每趟比较 length -1 - i 次
    //（第一趟确定一个最大值，第二趟则无需再比较length - 1的最后一次）
    //（第二趟确定一个第二大的值，则第三趟无需再比较length -2的倒数两次....）
  - 趟数
    - 如果一共有7趟，再第6趟的时候就已经全部排好了，那最后一趟就无需再比较
2. 在第一版中已经优化了每趟比较的次数，现在可以可以多余的趟数了
3. 如何找到某趟已经排好了？
  - 用一个标志位，进入 (趟数的循环) 默认为true，假设这趟已经排好了
  - 在（每趟次数的循环）中，比较相邻大小时，进入了判断，说明没有排好，标志位设置为 false
  - 在趟数循环的末尾，判断是不是标志位为true，为true表示该趟拍好了，break掉外层的趟数循环

4. 代码
const arr = [1, 4, 3, 2, 6, 5, 8, 7]
let out_count = 0
let in_count = 0
function bubble_sort(arr) {
  const len = arr.length - 1
  for (let i = 0; i < len; i++) { // ------------------- 总趟数 = 数组长度 - 1
    out_count++
    let isSortOk = true // ----------------------------- 标志位，默认是true，表示已经排好序了
    for (let j = 0; j < len - i; j++) { // ------------- 每趟比较的次数 = 总趟数 - 当前趟数
      in_count++
      if (arr[j] > arr[j + 1]) { // -------------------- 两两比较，前者大于后者，大的冒泡到后面
        isSortOk = false; // --------------------------- 进入了比较，说明该趟并未排好序，排好序了冒泡排序前面的不可能大于后面
        // 0. 注意：这里isSortOk一定要加分号！！！！！！
        // 1. 小括号或中括号开头的前一条语句末尾一定要加分号
        // 2. 或者在小括号或者中括号最前面加分号
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]] // - 交换位置
      }
    }
    if (isSortOk) {
      break; // 在趟数循环中，如果排好序，直接跳出整个外层循环，不再执行趟数的循环，即剩下的趟数不用再比较了
    }
  }
  return arr // 返回排好序的数组
}
const orderedArr = bubble_sort(arr)
console.log('orderedArr', orderedArr)
console.log('out_count', out_count)
console.log('in_count', in_count)

未做版本二优化时：out_count=7，in_count=28
做了版本二优化时：out_count=3，in_count=18
效果还是比较明显的

冒泡排序 - interview升华

问题：于冒泡排序，如何通过添加一个参数（函数），来控制升序和降序？
答案：

const arrs = [1, 3, 2, 5, 4]
function bubbling_sort (arr, compareFn) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i; j++) {
      if (compareFn(arr[j], arr[j+1]) > 0) { 
        // 其实就是在这里通过大于和小于来做升序和降序操作
        // arr[j] > arr[j+1] 交换后就是升序
        // arr[j] < arr[j+1] 交换后就是降序
        const temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
  return arr
}
const res = bubbling_sort(arrs, (a, b) =>  b - a)
// 即通过传入一个函数，比较这个函数中两个参数的大小来判断是升序还是降序
// 如果是 (a, b) => a - b 说明 前 > 后 ------------------------------- 升序
// 如果是 (a, b) => b - a 说明 后 > 前 ------------------------------- 降序
console.log(res)
image

(2) 快速排序 ( quick-sort )

快速排序

- 前置知识点：
1. pivot：基准

- 原理
1. 选择一个值为 pivot 基准值
2. 所有小于 pivot 的值，都放在左边
3. 所有大于 pivot 的值，都放在右边
4. 等于 pivot 的值可以放在左边，也可以放在右边，还可以再加一个数组，放中间
5. 不断重复以上步骤，直到所有子集只剩下一个元素为止



- 实现
const arr = [1, 3, 2, 6, 8, 5, 4, 7]
function quick_sort(arr) {
  const len = arr.length
  if (len <= 1) {
    return arr
    // 递归结束的条件，当 len < 1 时，不再需要把该数组划分成三个数组进行比较了，因为i数组中就一个值
    // 最终 三个数组拼接时都是有序的数组了
  }
  const pivot = Math.floor(Math.random() * len)
  // Math.random => [0, 1)
  // ( Math.random * arr.length ) => [0, 8)
  // 获取随机下标
  // 注意这里不能是 len-1，因为边界值，Math.random是[0, 1)，右边是开区间
  const left = []
  const middle = []
  const right = []
  for (let i = 0; i < len; i++) { // 这里 i < len 或者 i <= len 都可以
    if (arr[i] < arr[pivot]) {
      left.push(arr[i])
    }
    if (arr[i] > arr[pivot]) {
      right.push(arr[i])
    }
    if (arr[i] === arr[pivot]) {
      middle.push(arr[i])
    }
  }

  return quick_sort(left).concat(middle, quick_sort(right)) // 递归拼接数组
}

const orderedArr = quick_sort(arr)
console.log('orderedArr', orderedArr)
image

(3) 选择排序 ( selection-sort )

选择排序 selection-sort

原理：
1. 选取数组第一个元素（min），和余下的（数组Y）元素一一做对比（j），如果 j < min，则互换位置，直到Y循环完毕
2. 除去第一个元素，从剩下的数组中，选取第一个元素（min）和余下的数组（Y）一一做对比，重复以上步骤

代码：
const arr = [1, 4, 5, 3, 2, 6, 8, 7]
function select_sort(arr) {
  for(let i = 0; i < arr.length; i++) { // 循环的趟数
    let min = i // 标志位，用来存放最小值的下标，动态更改
    for(let j = i + 1; j < arr.length; j++) { // 循环除去第一个元素后的剩余数组，每一趟都能找到最小值，和第一个位置交换
      if(arr[j] < arr[min]) { // 剩余数组成员依次和第一个元素做对比，谁小就交换位置，该趟的最小值被交换到第一个成员位置
        min = j // 交换位置
      }
    }
    [arr[i], arr[min]] = [arr[min], arr[i]] // 交换位置对应的值，每趟找到最新元素位置后，都和第一个元素交换
  }
  return arr
}
const orderedArr = select_sort(arr)
console.log('orderedArr', orderedArr)
image

(4) 插入排序 ( insert-sort )

插入排序 insert-sort

原理：
1. 将数组看成两个部分，一个有序数组，和一个无序数组
2. 有序数组起始长度为1
3. 每次依次从无序数组取出第一个值，和有序数组的最后一个比较，如果该值小于有序数组最后一个值，最后一个值向后移一位
4. 有序数组是从后往前依次比较的，该循环需要满足的条件是j>=0 && 该项值 < 无序数组拿出来比较的值
5. 当有序数组循环比较完后，j+1的位置就是无序数组中拿出来的值需要插入到有序数组中的位置
6. 重复以上步骤

代码：
const arr = [1, 8, 4, 5, 7, 3, 2, 6]
function insert_sort(arr) {
  for (let i = 1; i < arr.length; i++) { // 无序数组拿出来比较的元素次数，即趟数，注意从1开始，即初始 ( 有序数组 ) 中有一个元素
    
    const cache = arr[i] 
    // 缓存每次从无序数组中取出来的 和有序数组进行比较的 元素
    // 注意：这里一定要缓存 arr[i]，如果不缓存 const cache = arr[i]，则每次在循环中打印arr[i]都是9
    // 不缓存的例子，见 【插入排序不缓存的bug】
    
    let j = i-1 // 有序数组末位位置
    while(j>=0 && arr[j] > cache) { // 循环需要满足的条件，从后往前循环有序数组，直到循环到最前面 并且 有序数组比较的值比无序中取出来的值大，就把有序的值往后移动1位
      arr[j+1] = arr[j] // 有序的值比cache大就往后移动一位
      j--
    }
    arr[j+1] = cache // arr[j+1]就是要插入的位置
  }
  return arr
}
const orderedArr = insert_sort(arr)
console.log('orderedArr', orderedArr)
image
image
image 
<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // insert-sort
      const arr = [1, 9, 8, 6, 7, 3, 2, 4, 5];

      const insert_sort = (arr) => {
        for (let i = 1; i < arr.length; i++) {
          const cache = arr[i];
          let j = i - 1;

          while (j >= 0 && arr[j] > arr[i]) {
            arr[j + 1] = arr[j];
            j--;
          }

          arr[j + 1] = arr[i];
          console.log(`i`, i);
          console.log(`cache`, cache);
          console.log(`arr[i]`, arr[i]); // --------------------------- 始终打印的是 9

          // [arr[j + 1], arr[i]] = [arr[i], arr[j + 1]];
        }

        return arr;
      };

      const res = insert_sort(arr);
      console.log(`res`, res);
    </script>
  </body>
</html>

(5) 希尔排序 (shell-sort )

希尔排序 shell sort


概念：
1. 希尔排序是插入排序的升级版
2. 希尔排序需要取间隔 gap，（将原数组风格成gap个组，然后对每个组进行插入排序）
3. 总的趟数：就是从原数组的gap位置开始，到元素组的最后位置
4. 总结：
希尔排序是按一定的间隔对数组进行分组，然后在每一个分组中做插入排序，然后逐次缩小间隔，
再在每一个分组中做插入排序，直到间隔为1时，结束整个函数
( 注意：gap的最小值一定要是1，即最后所有元素都只在一个数组内进行插入排序 )


复习一下插入排序：（ 看到了一个交换数组的方便写法 ）
1. 交换数组
  - [[a],  [b]] = [[b], [a]]解构的写法很直观和方便
2. 插入排序的原理：
  - 将原数组划分为两个区间，左边是排好序的数组，右边是未排好序的数组
  - 循环右边的数组，即是要比较的趟数
  - 循环左边的数组，分别和右边每趟数组第第一个元素比较
  - 左边数组从后往前循环，如果该次元素比右边数组的第一个元素大，该元素往后移动一位
  - 左边循环结束时，已经找到右边数组第一个元素需要插入的位置
  - 重复以上步骤
2. 插入排序代码：
const arr = [1, 4, 6, 3, 5, 2]
function insert_sort(arr) {
  for (let i = 1; i < arr.length; i++) { // 循环的趟数，即看作是右边的无序数组，从1开始，即左边数组有一个元素
    const temp = arr[i] // 缓存该第一个元素，因为左边数组的元素可能会右移一位
    let j = i - 1
    for (; j >= 0 && arr[j] > temp; j--) { // 左边数组，从后往前比较，大于缓存的值就右移动一位，则插入到该值前面
      arr[j+1] = arr[j] // 右移一位
    }
    arr[j+1] = temp // 条件不成立，即左边数组该值大于了temp，说明位置已经找到了，插入该值后面
  }
  return arr
}
const res = insert_sort(arr)
console.log(res, 'res')


-------

3. 希尔排序代码：
- 其实希尔排序只是在插入排序的基础上，分了若干个组，进行插入排序，在重复以上步骤，直到gap所有循环完
- 区间 gap的取值，一般都是  arr.length / 2
const arr = [1, 8, 3, 2, 6, 7, 5, 4]
function shell_sort(arr) {
  let gap = Math.floor(arr.length / 2) // 初始化gap，一般选的初始值是中间值
  for (; gap >= 1; gap = Math.floor(gap / 2)) {
    // 每趟 (插入排序) 范围都缩小一半，直到 gap 大于 0，( gap表示分成几组 )
    // 注意：gap最后一定是1，因为整个数组作为一个数组，要整个执行插入排序依次

    // 以下是插入排序的部分，只是每次的步调不是1，而是gap
    for (let i = gap; i < arr.length; i++) {
      // 插入排序，从 gap 开始
      // 从 gap 开始，到 gap + gap结束即到 arr.length结束
      const cache = arr[i] // 无序数组取第一个值
      let j = i - gap // 有序数组最后一个值

      // 有序数组从i-gap开始递减循环，直到 j >= 0
      for (; j >= 0 && arr[j] > cache; j = j - gap) {
        arr[j + gap] = arr[j] // 往后移动 gap 个位置
      }
      arr[j + gap] = cache // 无序取出的值要插入到有序部分的位置

      // 上面的for循环等价于：
      // for(; j >= 0; j = j - gap) {
      //   if (arr[j] > temp) {
      //       arr[j+gap] = arr[j]
      //   } else {
      //     break
      //   }
      // } 
      
    }
  }
  return arr
}
const orderedArr = shell_sort(arr)
console.log('orderedArr', orderedArr)
image
image
image

(6) 归并排序 ( merge-sort )

归并排序 merge-sort

原理：
1. 递归的将数组分隔成两个数组，递归结束条件是数组长度为1
2. 递归的从来个有序数组中取第一个元素，比较大小，合并到一个新的数组中，最后返回


------


代码：
const arr = [8, 1, 4, 2, 3, 5, 7, 6]

function merge_sort(arr) { // 归并排序
  if (arr.length <= 1) { // 递归结束的条件是，每个数组长度是 0 或者 1，不能再分就直接返回该数组
    return arr
  }

  let mid = Math.floor(arr.length / 2) // 中间值，通过中间值将数组分成两个数组
  const left = arr.slice(0, mid) // 左边的数组
  const right = arr.slice(mid) // 右边的数组

  return merge(merge_sort(left), merge_sort(right)) // merge_sort其实就是 ( 快速排序 )，可以保证 ( left ) 和 ( right ) 是有序的
}

function merge(left, right) { // 当merge执行的时候，已经是有序的数组了
  let result = [] // 最终返回的有序数组

  // 注意：left 和 right 要么是单个元素的数组，要么就是有序的数组 
  // 所以循环取出两个数组的第一项做比较，小的先进新数组
  // 条件是两个数组都有元素时
  while (left.length && right.length) { // 取完任意一个数组就停止push，注意：这里可能另一个数组还有值，所以有后续判断
    result.push(left[0] > right[0] ? right.shift() : left.shift())
  }

  // 当一个数组没有元素，而另外一个数组还有元素时，剩下的元素一定比新数组中的元素大
  // 因为上面的while循环中已经比较过了，小的都进新数组result中了
  // 所以下面直接拼接到最后面就行了，因为是最大的值
  result = result.concat(left.length ? left : right)

  return result
}

const orderedArr = merge_sort(arr)
console.log('orderedArr', orderedArr)
image

(7) 堆排序

堆排序 heap-sort

前置知识：
1. 二叉树
  - 节点 (i) 的 (左孩子2i)，(右孩子2i+1)   
2. 堆
  - 小根堆 - 比它的左右孩子小
  - 大根堆 - 比它的左右孩子大 
3. 完全二叉树
 - 根节点大于左右孩子节点，只有最后一排的孩子未满，并且左排列

4. 堆排序需要解决的两个问题？
  - 如何从一个无序数组构建成一个堆
    - 从完全二叉树的最后一个非叶子节点进行调整，因为页子节点已经是堆
    - 最后一个叶子节点n，那最后一个非页子节点就是 n/2
    - 具体步骤：
      1. 建立初始完全二叉树：将无序数组直接按顺序写成二叉树样式
      2. 从最后一个非叶子节点开始，往前依次进行调整（最后的叶子节点n, 那么就从 n/2开始）
      3. 如果要排成小根堆，就小的在上面，大根堆相反
  
  - 如何在取走堆顶元素后，调整剩余的元素形成一个新堆
    1. 输出堆顶元素后，以堆中最后一个元素替代之
    2. 然后将根节点值与左右子树的根节点值进行比较，并与其中小者进行交换
    3. 重复上述操作，直至下沉到( 叶子节点 )，将得到新的堆
    - 称这个从堆顶至页子的调整过程为 筛选

// 排序
function heapSort(arr) {
  var arr_length = arr.length
  if (arr_length <= 1) return arr
  // 1. 建最大堆
  // 遍历一半元素就够了
  // 必须从中点开始向左遍历，这样才能保证把最大的元素移动到根节点
  for (var middle = Math.floor(arr_length / 2); middle >= 0; middle--) maxHeapify(arr, middle, arr_length)
  // 2. 排序，遍历所有元素
  for (var j = arr_length; j >= 1; j--) {
    // 2.1. 把最大的根元素与最后一个元素交换
    swap(arr, 0, j - 1)
    // 2.2. 剩余的元素继续建最大堆
    maxHeapify(arr, 0, j - 2)
  }
  return arr
}
// 建最大堆
function maxHeapify(arr, middle_index, length) {
  // 1. 假设父节点位置的值最大
  var largest_index = middle_index
  // 2. 计算左右节点位置
  var left_index = 2 * middle_index + 1,
    right_index = 2 * middle_index + 2
  // 3. 判断父节点是否最大
  // 如果没有超出数组长度，并且子节点比父节点大，那么修改最大节点的索引
  // 左边更大
  if (left_index <= length && arr[left_index] > arr[largest_index]) largest_index = left_index
  // 右边更大
  if (right_index <= length && arr[right_index] > arr[largest_index]) largest_index = right_index
  // 4. 如果 largest_index 发生了更新，那么交换父子位置，递归计算
  if (largest_index !== middle_index) {
    swap(arr, middle_index, largest_index)
    // 因为这时一个较大的元素提到了前面，一个较小的元素移到了后面
    // 小元素的新位置之后可能还有比它更大的，需要递归
    maxHeapify(arr, largest_index, length)
  }
}

资料

上一篇下一篇

猜你喜欢

热点阅读