面试官：请用JS实现一个优先队列

先吐槽，最近面试真的好难！前端面试的源码部分和算法部分的题越来越多。上个月的四次面试，我两次被问到优先级队列的数据结构；幸好React源码的scheduler部分对小顶堆有一定的了解，有些地方比较模糊，现在简单说一下堆的数据结构，以及如何用JS;前端和优先队列。如果你看过React源码的Scheduler部分，应该对timerQueue延迟队列和taskQueue可执行队列有印象。它们都使用了小顶堆的优先级队列数据结构的实现，具体可以看《重学React之为什么需要Scheduler》。在Scheduler部分，这两个队列主要实现调度后的任务优先级排序（时间维度）；优先队列和堆优先队列顾名思义就是一个队列，队列有一个从头出队，从尾入队的原则；而优先队列每次出队列都是最大的（大顶堆）或者最小的（小顶堆），所以优先队列其实就是一个堆。堆是一种近似完全二叉树的数据结构。堆可以看作是一个数组。堆实际上是由一棵完全二叉树的结构维护的一维数组。根据排序方式的不同，可以分为大顶堆和小顶堆。大顶堆：每个节点的值都大于或等于其左右子节点的值小顶堆：每个节点的值都小于或等于其左右子节点的值如果将上面堆中的数组数据映射到数组中，然后这样//bigtoppile[50,45,40,20,25,35,30,10,15]//smalltoppile[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，就可以套用最后分页的公式childnode=(array.length+1)%2-1**当前节点的值与左子树节点的值比较，如果当前节点小于左子树的值，则交换当前节点和左子树；交换后检查左子树是否满足大顶堆的性质，如果不满足则重新调整子树结构；****然后比较当前节点的值和右子树节点的值。如果当前节点小于右子树的值，交换当前节点和右子树；然后重新调整子树结构；**当不需要交换调整时，会建立大顶堆constcreateHeap=(arr,)=>{constlength=arr.length//如果数组长度为0或1，直接返回不改变数组（不需要比较）if(length<=1)returnarr//通过下标遍历数组for(let我=1;我<长度；i++){while(i){//通过传入的数组下标获取父节点数组下标并比较替换constparentIndex=Math.floor((i-1)/2)//如果索引值对应当前数组下标大于父节点索引值对应的值，则替换//如果需要创建小顶堆，则arr[i]arr[parentIndex]){//使用解构赋值进行值替换[arr[i],arr[parentIndex]]=[arr[parentIndex],arr[i]]//完成替换，将当前i替换为parent下标，reduce比较i=parentIndex}else{//所有替换完成直接退出当前循环break}}}}如何向堆中插入数据？以上就是JS实现一个堆的过程，那么现在假设如果此时我们需要向堆中插入一条数据，应该如何操作呢？堆是一个优先级队列，所以我们每次插入或者取出元素都是从头部出队，从尾部入队；在每一步我们都需要比较和维护队列；插入操作如下图所示，所以我们可以先在队尾插入一个新元素，然后使用createHeap进行比较。constpush=(arr,value)=>{arr.push(value)createHeap(arr)returnarr}head元素出堆，因为优先队列被tail插入，head弹出。这时候如果我们需要弹出一个元素，如果是从头部弹出怎么办呢？首先，我们会弹出head元素，然后将tail元素填充到head，然后我们将head元素分别与左右子节点进行比较。如果只有一侧满足条件，则将其替换为满足条件的一侧。如果双方都满足条件条件是大的（或者小的，看是大顶堆还是小顶堆）一方出牌交换;如下图，9和13、15比较，都满足条件，15大于13，所以和15交换，然后9和子节点比较。和8比较不满足交换条件，和14比较满足交换条件，所以和14比较。14Swap；那怎么用js实现呢？//注意：需要传入创建的队列而不是数组constpeek=(arr)=>{constlength=arr.length//如果数组为空，直接返回nullif(!arr.length)returnnull//如果数组只有一个元素，则弹出并直接返回这个元素if(length===1)returnarr.pop()consttop=arr[0]//将最下面的子节点赋值给顶部节点arr[0]=arr.pop()letindex=0constlastIndex=length-1while(indexarr[findIndex]){findIndex=leftIndex}//如果右子节点的值大于父节点则交换节点（小顶堆为arr[leftIndex]arr[findIndex]){findIndex=rightIndex}//注意：以上两步是可以的，但目的是最大化（或minimum)节点转换为父节点，所以不影响//如果findIndex>index，说明子节点的值大于父节点，需要交换。swap完成后，需要从子节点开始比较，所以index=findIndexif(findIndex>index){[arr[findIndex],arr[index]]=[arr[index],arr[findIndex]]index=findIndex}else{//不满足交换条件，跳出循环break}}returntop}peek(arr)