二叉堆是一种应用很广的数据结构，今天，我们就来简单讲讲二叉堆。
什么是二叉堆？
二叉堆是一种特殊的堆。具有如下的特性：
具有完全二叉树的特性。堆中的任何一个父节点的值都大于等于它左右孩子节点的值，或者都小于等于它左右孩子节点的值。
根据第二条特性，我们又可以把二叉堆分成两类：
1、最大堆：父节点的值大于等于左右孩子节点的值。
2、最小堆：父节点的值小于等于左右孩子节点的值。
我们把二叉堆的根节点称之为堆顶。根据二叉堆的特性，堆顶要嘛是整个堆中的最大元素，要嘛是最小元素。
今天，我们主要来讲讲二叉堆的三个主要操作：
插入一个节点。删除一个节点。构建一个二叉堆。
不过这里需要注意的是，在二叉堆这种结构中，对于删除一个节点，我们一般删的是根节点。
下面我们以最小堆为例子，来讲讲这些操作。
插入一个节点。
刚才我们说二叉堆具有完全二叉树的特性，因此，我们在插入一个节点的时候，应该先保证节点插入后，它仍然是一颗完全二叉树，然后再来进行调整，使它满足二叉堆的另一个特性。
所以，在插入的时候，我们把新节点插到完全二叉树的最后一个位置。例如：
插入0。
之后我们再来进行调整，调整的原则是：让新插入的节点与它的父节点进行比较，如果新节点小于父节点，则让新节点上浮，即和父节点交换位置。
上浮之后继续和它的父节点进行比较，直到父节点的值小于或等于该节点，才停止上浮，即插入结束。例如：
0比5小，上浮。
0比2小于，上浮。
0比1小，上浮。
已经到达堆顶了，插入结束。
删除节点。
前面说了，删除节点一般删除的是根节点。
和插入一样，由于二叉堆具有完全二叉树的特性，因为删除时候，首先我们是要马上恢复它具有完全二叉树的特性，所以我们是采取这样的策略：把根节点删除之后，用二叉堆的最后一个元素顶替上来，然后在进行调整恢复。例如：
把0删除了之后，5替换上来。
之后再来调整，调整的规则和插入差不多类似，采取下沉的策略：让5和左右孩子节点相比较，如果左右节点有小于5的，则让那个较小的孩子代替5的位置，然后5下沉。
下沉之后，5继续和左右孩子相比，直到左右孩子都大于或等于5才结束。
如：5比1，3都大，1代替5的位置
5比4，2都大，2代替5的位置。
5已经不在具有左右孩子了，删除结束。
构建二叉堆
所谓构建，就是给你一个有n个节点的无序的完全二叉树，然后把它构建成二叉堆。
刚才我们在删除一个节点的时候，把最后一个元素补到根元素的位置上去，然后再让这个元素依次下沉，实际上，在这个元素还没有下沉之前，它就可以看作是一颗无序的完全二叉树了。
也就是说，要把一个无序的完全二叉树调整为二叉堆，我们可以让所有非叶子节点依次下沉。不过下沉的顺序不是从根节点开始下沉(想一下相必你就知道不能从根节点开始下沉)，而是从下面的非叶子节点下称，在依次往上。举个例子：
对于这样一颗无序的完全二叉树
8进行下沉。
接着，5进行下沉。
2没问题，之后让7进行下沉
调整完成，构建结束。
代码实现
不过这里需要说明的是，我们二叉树一般是采用链表的方式来实现的，但二叉堆我们是采用数组的方式来存储的。
如果知道了一个节点的位置，如何知道一个节点的左右孩子节点的位置呢？
这其实不难，根据完全二叉树的特点，假如一个节点的下标为n,则可以求得它左孩子的下标为：2*n+1；右孩子下标为：2*n+2。
下面是构建代码的实现：
publicclassBinaryHeap{//上浮操作，对插入的节点进行上浮/****@paramarr*@paramlength：表示二叉堆的长度*/publicstaticint[]upAdjust(intarr[],intlength){//标记插入的节点intchild=length-1;//其父亲节点intparent=(child-1)/2;//把插入的节点临时保存起来inttemp=arr[child];//进行上浮while(child>0&&temp<arr[parent]){//其实不用进行每次都进行交换，单向赋值就可以了//当temp找到正确的位置之后，我们再把temp的值赋给这个节点arr[child]=arr[parent];child=parent;parent=(child-1)/2;}//退出循环代表找到正确的位置arr[child]=temp;returnarr;}/***//***下沉操作，执行删除操作相当于把最后**一个元素赋给根元素之后，然后对根元素执行下沉操作*@paramarr*@paramparent要下沉元素的下标*@paramlength数组长度*/publicstaticint[]downAdjust(int[]arr,intparent,intlength){//临时保证要下沉的元素inttemp=arr[parent];//定位左孩子节点位置intchild=2*parent+1;//开始下沉while(child<length){//如果右孩子节点比左孩子小，则定位到右孩子if(child+1<length&&arr[child]>arr[child+1]){child++;}//如果父节点比孩子节点小或等于，则下沉结束if(temp<=arr[child])break;//单向赋值arr[parent]=arr[child];parent=child;child=2*parent+1;}arr[parent]=temp;returnarr;}/***构建操作**@paramarr*/publicstaticint[]buildHead(int[]arr,intlength){//从最后一个非叶子节点开始下沉for(inti=(length-2)/2;i>=0;i--){arr=downAdjust(arr,i,length);}returnarr;}}
本次讲解到此结束。下篇继续讲解和堆有关的知识点。至于bitmap算法优化的那篇，会在之后给出。
如果你觉得这篇内容对你挺有启发，为了让更多的人看到这篇文章：不妨
1、点赞、评论、收藏走一波，让更多的人也能看到这篇内容（收藏不点赞，都是耍流氓-_-）
3、关注我的公众号「苦逼的码农」，主要写算法、计算机基础之类的文章，里面已有100多篇原创文章
