最近写了一个请求，用到了优先级队列和二叉堆的相关知识。借此机会整理了一些关于二叉堆的知识，分享给大家。什么是优先队列？优先队列是数据结构中的一个基本概念。与先进先出（FIFO）出队顺序不同的是，它的出队顺序与元素的优先级有关。比如React的时间分片（ReactFiber），对渲染任务进行优先排序，出队的顺序与任务的“重要性”有关，所以满足这种情况的数据结构就是优先队列。优先级队列操作插入：在优先级队列中插入元素，使队列“排序”删除max/min：删除并返回最大/最小元素，使队列“排序”查找max/min关键字：find实现最大/最小值优先级队列比较优先级队列可以通过以上方式实现，优先级队列的主要操作是插入和删除，二叉搜索树和二叉堆这两个操作的时间复杂度是logn，但是二叉树在多次删除后容易倾斜，搜索成本也比二叉堆高，所以最终二叉堆更适合实现优先级队列的数据结构。二叉堆在二叉堆中的数组中，需要保证每个元素在特定位置小于（大于）或等于另外两个元素。比如下图中的树，父节点总是小于等于子节点。对于二叉堆，它有如下性质：节点k的父节点下标为k/2（向下取整）以某一个节点为根节点的子树，是该节点的极值二叉堆操作插入tree二叉堆的插入非常简单，只需要在二叉堆的末尾添加要插入的内容，并“浮动”到正确的位置即可。尝试在上面的二叉堆中插入一个新的元素9，过程如下：在末尾插入元素9，与父节点比较，顺序被破坏，将位置替换为父元素。替换成功后，继续上一轮操作，与父节点进行比较。如果订单仍然不满足，继续交换位置。再次更换后符合要求。程序框架函数push{*在堆的末尾添加元素*执行浮动循环*与父元素比较大小，将较大的放在父节点的位置returnminItem}实现函数push(heap:Heap,node:Node):void{constindex=堆。length;heap.push(node);//堆尾添加元素siftUp(heap,node,index);//浮动操作}functionsiftUp(heap,node,i){letindex=i;while(true){constparentIndex=(index-1)>>>1;//父节点位置：parentIndex=childIndex/2constparent=heap[parentIndex];if(parent!==undefined&&compare(parent,node)>0){//父节点更大。交换。heap[parentIndex]=node;heap[index]=parent;index=parentIndex;}else{//Theparentissmaller.Exit.return;}}}删除根节点的值比插入稍微复杂一点，可以总结为三步：取出根节点的值，用根节点替换最后一个元素，删除最后一个元素，下沉取出根节点。将最后一个元素与根节点交换并删除。对比发现订单被破坏，进行调整。彻底删除。程序框架函数pop{*设置minItem保存根节点*取出最后一个节点替换为根节点，删除最后一个节点*执行下沉循环*比较根元素与左右子节点，并选择较小的替换父节点的位置returnminItem}implementsexportfunctionpop(heap:Heap):Node|null{constfirst=heap[0];//取出根节点if(first!==undefined){constlast=heap.pop();//取出最后一个元素，删除if(last!==first){heap[0]=last;//反转根节点siftDown(heap,last,0);//sink}returnfirst;}else{returnnull;}}functionsiftDown(heap,node,i){letindex=i;constlength=heap.length;while(index
