上篇文章数据结构之二叉堆(优先队列)——原理解析详细介绍了二叉堆的实现原理，本篇文章在上篇文章的基础上，介绍二叉堆的建堆原理，二叉堆的入队和出队操作的java代码实现。
一丶二叉堆的存储结构
在上篇文章中，为了清晰的介绍二叉堆的原理，我们将二叉堆画出成了链式结构，链式结构涉及比较多的指针操作，因为二叉堆的具有完全二叉树的结构特性，更为简单的做法是将二叉堆的存储结构设计为数组。
图1 大根堆
对于如上图所示的二叉堆，利用数组来存树形结构如下所示。
图2 存储结构
可以看到其存储结构具有如下特点：
- 利用数组来存数大根堆其存储顺序和树的层次遍历顺序相同
- 数组的第一个元素(下标Index=0)不存放数据，重当哨兵元素，其具体作用后续会涉及。
- 在二根堆不断的入队和出队的操作下，数组中元素的数目会发生变化，必须设置一个指针，指向数组的边界元素。
- 二叉堆是具有堆序的完全二叉树，那么也满足完全二叉树的所有特点，可以知道对于完全二叉树的数组存储具有如下特点，对于数组中下标为i的元素，若其左孩子存在，那么其左孩子下标为2i，其右孩子若存在，下为2i+1，其父节点的坐标为i/2。这是一条非常重要的性质。
二丶二叉堆的建堆原理。
对于N个元素的建堆的过程等价于N个元素插入的过程，这是对二叉堆建堆过程最直观的理解，这里描述另外的一种方法。假如待建堆的数组如下，构建一个大根堆。
A={5,9,4,3,2,1}
-
依据待建堆数组构建一个随机完全二叉树，构建结果如下：
图3 随机完全二叉树 -
对于图3而言，已经满足了二叉树的结构特性了，只要完成二叉树的堆序特性，那么建堆的过程就算完成了。此时二叉树currentSize = 6，6这个下标指向堆尾元素1。i=currentSize/2=3,3这个下标指向堆尾元素1的父节点4，元素4也是最后一个非叶子节点。我们我们利用”下滤”操作调整元素4的堆序特性。结果如下图，其实元素4满足堆序特点，无需调整。
图4 第一次下滤调整 -
步骤2中i=3，指向元素4，此时i--，i=2指向元素9，继续利用下滤操作调整元素9的堆序特性结果如下：
图5 第二次堆序调整 -
i继续自减，i=2，指向元素5，此时利用”下滤”操作调整该元素的堆序特性，调整如下：
图3第三次堆序调整 - i继续自减，i=0发现数组已无元素可调，结束，建堆完成。
三丶二叉堆的java代码实现
//二叉堆--大根堆的java代码实现
//利用二叉堆完全树的结构特性我们利用数组来存储二叉堆。
public class BinaryHeap {
//currentSize数组的边界
intcurrentSize;
//储存二叉堆节点元素的数组
int[] item;
publicBinaryHeap(int [] data){
this.currentSize=data.length;
//实际上并不是乘5,这里乘5只是为了保证其具有足够的空间大小。
item = new int[(currentSize+1)*5];
//这里特别注意，数组的第一个元素并不存数数据
//直接复制构建一棵随机完全二叉树
for(int i =0;i<data.length;i++){
item[i+1] = data[i];
}
//对构成的随机完全二叉树进行堆序的调整
buildHeap();
}
//建堆操作的原理：对随机完全二叉树的每个非叶子节点完成下滤操作。
privatevoid buildHeap(){
if(item==null||item.length<=0){
return ;
}
for(int i =currentSize/2;i>0;i--){
percolateDown(i);
}
}
//index:指定下滤的元素下标
privatevoid percolateDown(int index) {
intcopy = item[index];
intchild=0;
for(int i = index;i*2<=currentSize;i=child){
//child指向左节点。
child = i*2;
//这需要判断该节点是否存在右孩子
int max = item[child];
if(child+1<=currentSize&&max<item[child+1]){
//++child指向右节点
max = item[++child];
}
if(copy<max){
//不满足堆序性质，覆盖
item[index] = max;
}else{
//满足堆序性质，结束该次堆调整。
item[i] = copy;
return ;
}
}
}
@Override
publicString toString() {
return"BinaryHeap [item=" + Arrays.toString(item) + "]";
}
publicvoid insert(int element){
currentSize++;
item[currentSize] = element;
//数组元素0这里有个哨兵。
item[0] = element;
intparent = 0;
for(int i = currentSize;i>0;i =parent){
parent = i/2;
if(item[parent]<item[0]){
item[i] = item[parent];
}else{
item[i] = item[0];
item[0] = 0;
return;
}
}
}
publicint deleteMax(){
intdata = item[1];
item[1] = item[currentSize--];
percolateDown(1);
returndata;
}
publicstatic void main(String [] args){
int[] data = new int[]{5,9,4,3,2,1};
BinaryHeap heap = new BinaryHeap(data);
heap.insert(10);
System.out.println(heap.toString());
System.out.println(heap.deleteMax());
System.out.println("-----------------------");
System.out.println(heap);
}
}
