二叉堆的构建，上浮以及下沉

二叉堆本质上就是完全二叉树，分为两类

1. 最大堆，所有的父节点都大于或等于它的左右孩子节点
2. 最小堆，所有的父节点都小于或等于它的左右孩子节点

以下代码都是以最小堆为例

二叉堆的操作

二叉堆虽然是一个完全二叉树，但是它的存储方式并不是链式存储，而是顺序存储，它所有的节点都存储在数组中。

父节点与孩子节点，父节点与父节点的父节点在数组中坐标的关系推导

插入节点

插入的节点存放在二叉堆的最后一个位置，然后将这个节点与它的父节点比较，不满足最小堆性质的就将二者交换，这就是“上浮”，再与新的父节点比较，直至上浮到正确位置

/*** 上浮 插入时用上浮* @param array 待调整的堆*/
public static void upAdjust(int[] array){int child = array.length-1;int parent = (child-1)/2;//存放插入的节点数值，用于最后交换int temp = array[child];while(child>0&&temp<array[parent]){//有了temp就不需要交换，只需覆盖最后跳出while时再把temp放在该放的位置array[child]=array[parent];//父节点变为孩子节点child = parent;// 父节点的父节点parent=(child-1)/2;}array[child]=temp;
}

删除节点

二叉堆所删除的是出于堆顶的节点，为了维持二叉树的结构，会将最后一个节点临时补到堆顶的位置，然后依次和左右孩子比较进行下沉操作。

/*** 下沉，删除时用下沉* @param array 堆* @param index 要下沉的父节点* @param length 堆的有效大小*/
public static  void downAdjust(int[] array,int index,int length){//左孩子节点int child = 2*index+1;//临时存放父节点的值用于最后的交换int temp=array[index];//判断是否存在左孩子节点while(child<length){//判断是否存在右孩子节点，并且右孩子节点并且左孩子节点大于右孩子节点if(child+1<length&&array[child]>array[child+1]){child++;}//判断父节点是否小于右孩子节点，小于就跳出if(temp<=array[child]){break;}// 与上浮一样不交换直接覆盖array[index] = array[child];index = child;child = index*2+1;}array[index] = temp;
}

构建二叉堆

构建二叉堆是将一个无序的完全二叉树调整为二叉堆，本质就是让所有的非叶子节点依次下沉。从二叉树的最后一个非叶子节点开始。

/*** 构建堆  将一个无序的完全二叉树调整为二叉堆，让所有的非叶子节点依次下沉* @param array*/
public static void buildHeap(int[] array){//从二叉堆最后一个非叶子节点开始，让所有非叶子节点依次下沉for (int i = (array.length-2)/2; i >=0 ; i--) {downAdjust(array,i,array.length);}
}