二叉堆是完全二叉树，或者近似完全二叉树
若一棵二叉树至多只有最下面两层的结点的度数可以小于2，并且最下层的结点都集中在该层最左边的若干位置上，则此二叉树为完全二叉树。

二叉树：可以用数组来表示一棵数，如果已经根节点的下标为i，那么它的俩个子节点下标分别为2i+1和2i+2。

二叉堆特征：1、父节点的键值总是大于或等于（小于或等于）任何一个节点的键值；2、每个节点的左子数和右子树都是一个二叉堆
任意节点的值都大于其子节点的值--大顶堆 ；任意节点的值都小于其子节点的值--小顶堆

java">public class Test4 {public static void main(String[] args) {int[] arr = new int[]{65,33,67,9,34,1,56,76,43};//f3(arr);f4(arr);for (int i : arr) {System.out.print(i+" ");}}//堆排序：先把数组堆化，在进行排序，堆的高度为lg(n) ,时间复杂度O(nlg(n))//把数组堆化：//1、构建最小堆static void makeMinHeap(int[] arr){for(int i=arr.length/2-1;i>=0;i--){minHeap(arr,i,arr.length);  //从最后一个有子节点的父节点开始。因为左右子节点下标为2i+1或2i+2，所以数组后半段不可能有父节点。}}static void minHeap(int[] arr,int i,int length){int j=2*i+1;  //左节点int temp = arr[i]; //父节点while(j<length){if(j+1 <length && arr[j+1]<arr[j])j++; //找到左右节点中较小的。if(arr[j]<temp){ //如果子节点比父节点还小，就子节点上移到父节点arr[i]=arr[j];i=j;    //然后把较小节点当作父节点，在找较小子节点j=2*i+1;}else{break;}}arr[i] = temp;}//2、构建最大堆static void makeMaxHeap(int[] arr){for(int i=arr.length/2-1;i>=0;i--){maxHeap(arr,i, arr.length);}}static void maxHeap(int[] arr,int i,int length){int j=2*i+1;  //左节点int temp = arr[i]; //父节点while(j<length){if(j+1 <length && arr[j+1]>arr[j])j++; //找到左右节点中较大的。if(arr[j]>temp){ //如果子节点比父节点还大，就子节点上移到父节点arr[i]=arr[j];i=j;    //然后把较大节点当作父节点，在找较大子节点j=2*i+1;}else{break;}}arr[i] = temp;}//对堆降序排序static void f3(int[] arr){//最小堆化makeMinHeap(arr); //此时0下标元素一定为最小值，把该元素与最后一个元素交换位置。for(int i= arr.length-1;i>0;i--){swap(arr,0,i);minHeap(arr,0,i);  //然后缩小范围，再次最小堆化，不包括最后一个元素}}//对堆升序排序static void f4(int[] arr){//最小堆化makeMaxHeap(arr); //此时0下标元素一定为最小值，把该元素与最后一个元素交换位置。for(int i= arr.length-1;i>0;i--){swap(arr,0,i);maxHeap(arr,0,i);  //然后缩小范围，再次最小堆化，不包括最后一个元素}}//交换元素static void swap(int[] arr,int i,int j){int t=arr[i];arr[i]=arr[j];arr[j]=t;}
}