withJS节点组成，如下图所示。每个分支节点也常被称为子树，二叉堆是属于完全二叉树的一种特殊树。二叉树和二叉堆的关系在日常工作中，会遇到很多数组操作，比如排序。那么了解二叉堆的实现，对以后的开发效率有一定的提升。这里简单介绍一下什么是二叉树，什么是二叉堆。二叉树的特点根节点：二叉树的最顶层节点分支节点：除了根节点还有叶子节点叶子节点：除了自己，没有其他子节点在二叉树中，我们经常使用父节点和子节点来描述，比如上图左边节点2是6和3的父节点，否则6和3是2的子节点二叉树的分类二叉树分为满二叉树（fullbinarytree）和完全二叉树（completebinarytree）。满二叉树：深度为k，有2^k-1个节点的二叉树称为满二叉树。完全二叉树：完全二叉树是指最后一层左边是满的，右边可能满也可能不满，然后剩下的层都是满二叉树，称为完全二叉树（满二叉树也是完全二叉树）。从图中我们可以看出二叉树是按照从上到下的顺序排列的。可以想象，可以用一个数组来表示二叉树的结构，从下标index(0-8)从上到下依次排列。二叉树的左节点表达式索引*2+1。例如：以根节点为例求左节点，根节点的下标为0，则左节点的序号为1，数组中对应的值为1。右节点表达式二叉树的索引为index*2+2。例如：以根节点为例求右节点，根节点的下标为0，则右节点的序号为2，取值对应数组中有8个二叉树叶子节点表达式序号>=floor(N/2)都是叶子节点（N为数组长度）。例如：floor(9/2)=4，那么从下标4开始的值都是叶子节点二叉堆的特征二叉堆是一棵完全二叉树，父节点和子节点必须保持固定的顺序关系，并且每个节点的左右子树都是二叉堆。从上图可以看出图1：每个父节点都大于等于子节点，满足二叉堆的性质图2：如果其中一个父节点小于子节点，则不满足二叉堆性质二叉堆分类二叉堆根据排序的不同可以分为最大堆和最小堆：根节点的键值是所有堆节点的键值中最大的，并且每个父节点的值都大于子节点的值最小堆：根节点的键值是所有堆节点键值中最小的，每个父节点的值都小于子节点的值.如何实现二叉堆通过上面的描述，想必大家对二叉堆有了一定的了解。那么接下来就是如何实现了。以最大堆为例，先初始化数组，然后交换位置形成最大堆。初始化二叉堆从上面的描述我们可以知道，二叉堆其实就是一个数组，所以初始化非常简单。classHeap{constructor(arr){this.data=[...arr];this.size=this.data.length;}}父子节点交换位置图1中，2被认为是父节点小于子节点，显然不符合最大堆性质。maxHeapify函数可以改变每个不满足最大堆属性的节点的位置，从而满足最大堆属性数组。调整步骤：调整分支节点2的位置（不满足最大堆性质）获取父节点2的左右节点（12、5），从（2、15、5）比较，找出最大的node并与父节点交换，如果该节点本身是最大节点，则停止操作，重复step2的操作，从2,4,7中找出最大值与2交换（递归）maxHeapify(i){letmax=i;if(i>=this.size){return;}//当前序号的左节点constl=i*2+1;//当前需要的右节点constr=i*2+2;//在当前节点及其左右节点中求最大值if(lthis.data[max]){max=l;}if(rthis.data[max]){max=r;}//最后的max节点是自己，那么最大堆属性已经满足，停止运行if(max===i){return;}//用最大值节点交换父节点constt=this.data[i];this.data[i]=this.data[max];this.data[max]=t;//递归继续执行returnthis.maxHeapify(max);}形成最大堆我们可以看到初始化是通过一个数组来完成的，如下图，显然不满足最大堆的性质。上面的maxHeapify函数只是交换了某个节点，并不能重构整个数组，所以我们需要依次递归重构数组。找到所有分支节点Math.floor(N/2)(不包括叶子节点)对找到的子节点进行maxHeapify操作rebuildHeap(){//叶子节点constL=Math.floor(this.size/2);for(leti=L-1;i>=0;i--){this.maxHeapify(i);}}生成升序数组。swap函数交换第一个位置和最后一个从堆中取出相当于size-1。执行maxHeapify函数比较根节点找到最大值并交换最终数据将成为升序数组sort(){for(leti=this.size-1;i>0;i--){swap(this.data,0,i);this.size--;this.maxHeapify(0);}}插入方式使用Insert函数作为插入节点的函数，首先在数据的末尾插入节点，因为节点是追加的，size+1因为一个父节点有2个子节点，我们根据这个性质，可以通过isHeap函数得到第一个叶子节点，而新插入的节点可以通过第一个叶子节点得到，然后比较三个值，找出最大值，确定插入节点。如果与父节点相同，则不进行重构（等于满足二叉堆性质），否则进行rebuildHeap。isHeap(){constL=Math.floor(this.size/2);for(leti=L-1;i>=0;i--){constl=this.data[left(i)]||Number。MIN_SAFE_INTEGER;constr=this.data[right(i)]||Number.MIN_SAFE_INTEGER;constmax=Math.max(this.data[i],l,r);if(max!==this.data[i]){returnfalse;}returntrue;}}insert(key){this.data[this.size]=key;this.size++if(this.isHeap()){return;}this.rebuildHeap();}删除methoddelete函数作为删除节点，先删除index中传入的节点，因为节点被删除，size-1重复上面插入节点的操作delete(index){if(index>=this.size){return;}this.data.splice(index,1);this.size--;if(this.isHeap()){return;}this.rebuildHeap();}完整代码/***最大堆*/functionleft(i){return(i*2)+1;}functionright(i){return(i*2)+2;}functionswap(A,i,j){constt=A[i];A[i]=A[j];A[j]=t;}classHeap{constructor(arr){this.data=[...arr];this.size=this.data.length;this.rebuildHeap=this.rebuildHeap.bind(this);this.isHeap=this.isHeap.bind(this);this.sort=this.sort.bind(this);this.insert=this.insert.bind(this);this.delete=this.delete.bind(this);this.maxHeapify=this.maxHeapify.bind(this);}/***重结构堆，形状最大堆*/rebuildHeap(){constL=Math.floor(this.size/2);for(leti=L-1;i>=0;i--){this.maxHeapify(i);}}isHeap(){constL=Math.floor(this.size/2);for(leti=L-1;i>=0;i--){constl=this.data[left(i)]||Number.MIN_SAFE_INTEGER;constr=this.data[right(i)]||Number.MIN_SAFE_INTEGER;constmax=Math.max(this.data[i],l,r);if(max!==this.data[i]){returnfalse;}returntrue;}}sort(){for(leti=this.size-1;i>0;i--){swap(this.data,0,i);this.size--;this.maxHeapify(0);}}insert(key){this.data[this.size++]=key;if(this.isHeap()){return;}this.rebuildHeap();}delete(index){if(index>=this.size){return;}this.data.splice(index,1);this.size--;if(this.isHeap()){return;}this.rebuildHeap();}/***交换父子节点位置，符最大堆特征*@param{*}i*/maxHeapify(i){letmax=i;if(i>=this.size){return;}//求左节点中比较大的序号constl=left(i);constr=right(i);if(lthis.data[max]){max=l;}if(rthis.data[max]){max=r;}//如果当前节点最大，则已经是最大堆if(max===i){return;}swap(this.data,一世，最大值）；//继续向下递归执行returnthis.maxHeapify(max);}}module.exports=Heap;例子相信大家通过上面的描述对最大堆的实现有了一定的了解，我们可以以此来排序constarr=[15,12,8,2,5,2,3,4,7];constfun=newHeap(arr);fun.rebuildHeap();//形成最大堆的结构fun.sort();//通过排序，生成一个升序数组console.log(fun.data)//[2,2,3,4,5,7,8,12,15]总结文章主要介绍二叉树和二叉堆的概念，然后通过代码实现二叉堆。我们可以通过二叉堆来做排序和优先级队列。
