本文转载自微信公众号《JS日报》，作者灰灰。转载本文请联系JS每日一问公众号.1、什么是堆（Heap）是计算机科学中一种特殊类型数据结构的总称？堆通常是一个数组对象，可以看做是一棵完全二叉树，如下图所示：它总是满足如下性质：堆中的某个结点的值总是不大于或不小于大于其父节点值的堆总是一个完全二叉树堆，可分为最大堆和最小堆：最大堆：对于每个根节点，都有一个根节点的值大于最小堆的值两个子节点的：每个根节点都有一个根节点，其值小于子节点的值。2、操作堆的元素存储方式，按照完全二叉树的顺序，采用一维存储方式存储。在数组中，如下图：一维数组中存储如下：[0,1,2,3,4,5,6,7,8]根据完全二叉树的特点，可以得到如下特征：数组的零坐标编码为堆顶元素一个节点的父节点坐标等于它的坐标除以2整数部分一个节点的左节点等于自己的节点坐标*2+1一个节点的右节点等于自己的节点坐标*2+2根据上面堆的特点，构造最小堆的构造函数和对应的属性方法如下：classMinHeap{constructor(){//存储堆元素this.heap=[]}//获取父元素坐标getParentIndex(i){return(i-1)>>1}//获取左节点元素坐标getLeftIndex(i){returni*2+1}//获取右节点元素坐标getRightIndex(i){returni*2+2}//交换元素swap(i1,i2){consttemp=this.heap[i1]this.heap[i1]=this.heap[i2]this.heap[i2]=temp}//查看堆顶元素peek(){returnthis.heap[0]}//获取堆元素大小size(){returnthis.heap.length}}与堆相关的操作有：插入，删除，插入，将值插入到堆的底部，也就是数组的尾部，当有新元素插入时，堆的结构被改变了就会被销毁，所以需要将堆中的一个元素向上移动，与它的父节点交换这个值，直到父节点小于等于插入的值。在大小为k的堆中插入一个元素的时间复杂度为O(logk)如下图，节点22为新插入的元素，然后向上移动：相关代码如下：//insertelementinsert（值）{this.heap.push（值）this.shifUp(this.heap.length-1)}//向上操作shiftUp(index){if(index===0){return}constparentIndex=this.getParentIndex(index)if(this.heap[parentIndex]>this.heap[index]){this.swap(parentIndex,index)this.shiftUp(parentIndex)}}删除一个常见的操作是将堆顶替换为数组尾部的元素。这里并没有直接删除堆顶，因为所有的元素都会向前移动一位，会破坏堆的结构再向下移动，与它的子节点交换新的堆顶，直到子节点大于或等于新的堆顶。删除堆顶的时间复杂度为O(logk)整体运行如下图所示：相关代码如下：//deleteelementpop(){this.heap[0]=this.heap.pop()this.shiftDown(0)}//降档操作shiftDown(index){constleftIndex=this.getLeftIndex(index)constrightIndex=this.getRightIndex(index)if(this.heap[leftIndex]
