关键点 ：
- 平衡二叉树；
- 任意父节点都大于（小于）子节点；
- 用数组来储存。(父节点为arr[i]，则左节点arr[i<<1+1]，右节点arr[i<<1+2];)
思路：
1:构建最大顶堆；
2:取出最大顶的“顶”，调整堆；
public class ArrayHeap {
private void initHeap(int[] arr,int length) {
if (arr==null||arr.length==0) {
return;
}
int num = length/2-1;
for( ;num>=0;num--){
adjustHeap(arr, num, length);
}
}
private void adjustHeap(int[] arr, int index,int length) {
if (arr==null||arr.length==0||index<0||index>length||lastIndex<0||length>arr.length) {
return;
}
int temp = arr[num];
while (2*index+1<=length) {
int left = index<<1+1;
int right = left+1;
int maxsonindex = right<=length?arr[left]>arr[right]?left:right:left;
if (arr[index]<arr[maxsonindex]) {
swap(arr[index], arr[maxsonindex]);
}
index+=index;
}
}
private void swap(int a,int b) {
a = a + b;
b = a - b;
a = a - b;
}
public void heapSort(int[] arr) {
if (arr==null||arr.length==0) {
return;
}
int length = arr.length;
initHeap(arr,length);
for(int i = 0;i<length-1;i++){
swap(arr[0], arr[length-1-i]);
adjustHeap(arr, 0, length--);
}
}
}
