關(guān)鍵點(diǎn) ：
- 平衡二叉樹砸泛；
- 任意父節(jié)點(diǎn)都大于（小于）子節(jié)點(diǎn)耕腾；
- 用數(shù)組來儲(chǔ)存榕暇。(父節(jié)點(diǎn)為arr[i]蓬衡，則左節(jié)點(diǎn)arr[i<<1+1]喻杈，右節(jié)點(diǎn)arr[i<<1+2];)
思路：
1:構(gòu)建最大頂堆；
2:取出最大頂?shù)摹绊敗闭恚{(diào)整堆筒饰；
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--);
}
}
}
