用数组得有序下标来表示完全二叉树得节点值 ，那么i位置得左子节点下标为2*i+1;右子节点下标为2*i+2; 父节点下标为(i-1)/2
大根堆：父节点得值大于子节点；树得最大值为头节点得值；
小根堆：父节点得值小于子节点；同理树得最小值为头节点得值。
那么如何将一个完全二叉树即一个已知大小得数组构成一个大根堆？
完成第一个需求:每出现一个数便就让其构成到大根堆当中
注：(0-1)/2 == 0
// 每出现一个数，将其构造成大根堆
public static void heapInsert(int[] arr,int index){
while(arr[index] > arr[(index-1)/2]){
swap (arr,index,(index-1)/2);
index = (index-1)/2; // 下标上移到父节点 一次判断
}
}
swap 是定义的交换
// 数组中得两个值做交换
public static void swap(int[] arr,int i , int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
完成这样一个需求：在已知的大根堆当中找出最大值，
这个可以很明显得到那边就是根的头节点，那么将这个头节点去除掉，如何再次将这个堆构建成大根堆呢？
我们这是可以将这个树中的最后一个子节点赋值到头节点当中，再让堆的大小heapSize--,即这样从逻辑上删除了一个元素，删除了头节点的值，并且将末尾的哪个树放入到了头节点上；那么此时需要做的就是如何让头节点的这个这个值，与下面的节点值比较并形成大根堆呢？
1.首先找出当前节点的两个子节点中最大值的下标值
2.将这个值与当前节点值比较 如果当前节点值更大，说明其找到了位置，若这个值小于了子节点的最大值，那么将index索引向下移动
public static void heapify(int[] arr, int heapSize,int index){
int left = index*2+1; //定义左子节点
while(leftarr[left] ? left+1 : left;
// 子节点最大值在和当前节点比较 得出较大值得那个节点
largeIndex = arr[index] > arr[largeIndex] ? index : largeIndex;
if(index == largeIndex){
// 说明当前节点不用往下走了 与子节点比较的过程当中最大的哪个值就是本身自己 直接break
break;
}
// index != largeIndex
// 此时说明index需要往下走了
swap (arr,index,largeIndex);
// 将下标 依次下移
index = largeIndex;
left = index*2 + 1;
}
}
第三个需求：如果在堆的中间改变了一个值，那么如何让其有效更改并且再次构成大根堆呢？
其实此时该节点的值只需要分别进行上述的heapInsert、heapify；因为当前的节点值无论怎么改变都只会有两种情况：
1.大于头节点 即执行heapInsert 找到对应位置后执行heapify但不改变位置，因为此时已经是大根堆了；
2.小于子节点 执行heapify找到对应位置，同理执行heapInsert不改变位置已经找到了对应的位置,直到最后一个节点进行heapify
那么堆排序代码：
public static void heapSort(int[] arr){
if(arr == null || arr.length <= 1){
return;
}
// 构成大根堆
for(int i = 0 ; i < arr.length ; i++){
heapInsert (arr,i);
}
// 构成有序
int heapSize = arr.length;
swap (arr,0,--heapSize);
while(heapSize > 0){
heapify (arr,0,heapSize);
swap (arr,0,--heapSize);
}
}
复杂度分析
事件复杂度 为 nlogn 空间复杂度为1
对于构造大根堆的分析
可以不用每次都看成插入一个值来进行构造大根堆，而是可以看成初始的一个数组就是一个完全二叉树，那么我们需要的就是将一个完全二叉树构造成一个大根堆
思路：从完全二叉树的最后往前遍历每一个元素尽心一次heapify操作，即就是将当前节点所在的树构成大根堆
代码：
for(int i = arr.length ; i >= 0 ; i--){
heapify (arr,i,arr.length);
}
当前i的起始位置不一定是要在树的最后 可以是在倒数的第二层节点，因为最后一层节点都是没有子节点的而最后一层的节点数最多为 heapSize/2 + 1
