关于javascript:面试官请使用JS实现一个优先队列

首先吐槽先最近面试真的好难！前端面试源码局部和算法局部问的越来越多。

在上个月的四次面试中对于 优先队列 这种数据结构被问到了两回；还好之前看过局部 React 源码的 scheduler 局部对 小顶堆 有一些了解，不置可否的说出一部分，当初简略讲讲堆这种数据结构，以及用 JS 如何实现；

如果你看过 React 源码的 Scheduler 局部，你应该会对 timerQueue 延时队列 与taskQueue 可执行队列 有所印象，他们均是采纳 小顶堆 这种优先队列数据结构来实现的具体可看《重学 React 之为什么须要 Scheduler》，在 Scheduler 局部这两个队列次要是做到了调度后的工作优先级排序（工夫维度）；

优先队列 顾名思义就是一个队列，队列有一个准则就是从头部出队从尾部入队；而优先队列每次出队入队都是最大(大顶堆) 或者最小值（小顶堆），因而优先队列实际上也是一个堆。而堆是一种近似 齐全二叉树 的数据结构，堆能够看作是一个数组，堆其实就是利用齐全二叉树的构造来保护的一维数组 ，依据排序形式不同能够分为 大顶堆 与小顶堆，

大顶堆：每个节点的值大于或等于其左右孩子节点的值
小顶堆：每个节点的值小于或等于其左右孩子节点的值

如果将上图堆中数组数据映射到数组中则是这样子的

// 大顶堆
[50,45,40,20,25,35,30,10,15]
// 小顶堆
[10,20,15,25,50,30,40,35,45]

因而咱们依据以上堆的节点值与数组中的下标咱们能够得出以下两个公式

大顶堆： arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆： arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

如果当初咱们有一个无序的纯数字的数组，咱们将如何对它进行堆排序呢？假如咱们当初有一个无序数组
`[3, 7, 16, 10, 21, 23]
` 咱们须要对他进行堆排序(大顶堆) 那么咱们须要怎么做呢？

咱们须要从最初一个 分叶子节点 开始从下往上进行调整；

Q: 如何查找最初一个分叶子节点?

A: 因为咱们用一维数组来存储堆里的数据，所以咱们能够取数组的长度 +1/ 2 取整数 -1，假如咱们的数组名为 array，则能够套用公式最初一个分页子节点 = (array.length+1)%2 – 1

** 比拟以后节点的值和左子树节点的值，如果以后节点小于左子树的值，就替换以后节点和左子树；
替换完后要查看左子树是否满足大顶堆的性质，不满足则从新调整子树结构；**

** 再比拟以后节点的值和右子树节点的值，如果以后节点小于右子树的值，就替换以后节点和右子树；
替换完后要查看右子树是否满足大顶堆的性质，不满足则从新调整子树结构；**

无需替换调整的时候，则大顶堆构建实现

图片与内容摘自图解大顶堆的构建、排序过程

const createHeap = (arr,)=>{
    const length = arr.length
    // 如果数组长度为 0 或者 1 则不扭转数组间接返回(无需比拟)
    if (length <= 1) return arr
    // 通过数组下标遍历
    for (let i = 1; i < length; i++) {while (i) {
            // 通过传入的数组下标获取父级节点数组下标并进行比对替换
            const parentIndex = Math.floor ((i - 1) / 2)

            // 若以后数组下标对应的索引值大于父级节点索引值对应的值则替换
            // 如果须要创立的是一个小顶堆则 arr[i]<arr[parentIndex]
            if (arr[i]>arr[parentIndex]) {
                // 利用解构赋值进行值替换
                [arr[i], arr[parentIndex]] = [arr[parentIndex], arr[i]]
                // 替换实现将以后 i 替换成父级下标，缩小比对
                i = parentIndex
            } else {
                // 所有替换实现间接退出以后循环
                break
            }
        }
    }
}

以上是 JS 实现一个堆的过程，那么当初假如如果此时咱们须要向堆中插入一条数据咱们该如何操作？

堆是一个优先队列，所以咱们每次咱们插入或者取出元素的时候都是从头部出队，从尾部入队；在每一步咱们都须要进行比拟放弃队列；
插入操作如下图

因而咱们能够先在队列尾部插入新元素，而后再用 createHeap 进行比对

const push = (arr,value)=>{arr.push(value)
    createHeap(arr)
    return arr
}

因为优先队列是由尾部插入头部弹出的，此时如果咱们须要弹出一个元素则会从头部弹出须要怎么操作？
首先咱们会将头部元素弹出，而后将尾部元素填充至头部

再而后咱们将头部元素与左右两边子节点别离进行比拟，如果只有一边符合条件则与符合条件的一方替换，如果两边都符合条件则与较大 (或较小，取决于是大顶堆还是小顶堆) 的一方进行对调；

如下图，9 与 13 和 15 进行比拟，均符合条件，15 大于 13 所以与 15 对调

而后 9 再与子节点进行比拟，与 8 比拟不合乎交换条件，与 14 比拟合乎交换条件，因而与 14 对调；

那么用 js 如何实现？

// 留神：需传入已创立队列而不是数组
const peek = (arr)=>{
    const length = arr.length
    // 若数组为空则间接返回 null
    if (!arr.length) return null
    // 若数组只有一个元素则间接弹出返回这个元素
    if (length === 1) return arr.pop()
    const top = arr[0]
    // 将底部子节点赋值到顶部节点
    arr[0] = arr.pop ()
    let index = 0
    const lastIndex = length - 1
    while (index < lastIndex) {
        let findIndex = index
        let leftIndex = index * 2 + 1
        let rightIndex = index * 2 + 2
        // 如果左侧子节点值大于父节点则进行节点对调(小顶堆为 arr[leftIndex]<arr[findIndex])
        if (leftIndex <= lastIndex && arr[leftIndex]> arr[findIndex]) {findIndex = leftIndex}
        // 如果右侧子节点值大于父节点则进行节点对调(小顶堆为 arr[leftIndex]<arr[findIndex])
        if (rightIndex <= lastIndex && arr[rightIndex]>arr[findIndex]) {findIndex = rightIndex}

        // 注: 以上两步有都执行的可能，然而目标都是为了将最大（或者最小）节点兑换到父节点, 所以不影响

        // 如果 findIndex > index 则阐明子节点值大于父节点须要进行对调，对调实现之后须要从子节点进行比拟因而须要 index = findIndex
        if (findIndex > index) {[arr[findIndex], arr[index]] = [arr[index], arr[findIndex]]
            index = findIndex
        } else {
            // 不合乎对调条件，跳出循环
            break
        }
    }
    return top
}
peek(arr)

关于javascript:面试官请使用JS实现一个优先队列

前端与优先队列

优先队列与堆

如何创立一个堆？

如何用 JS 创立一个堆？

如何向堆中插入数据？

头部元素出堆操作