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)