//第六天，堆排序
import java.util.Arrays;
public class heapSort_day6 {
static final int Max=10;
private int[] arr;
public heapSort_day6(int[] arr){
this.arr = arr;
}
public void sort(){
int len = arr.length - 1;
int beginIndex = (len - 1) >> 1;
for(int i = beginIndex; i >= 0; i--){
maxHeapify(i, len);
}
for(int i = len; i > 0; i--){
swap(0, i);
maxHeapify(0, i - 1);
}
}
private void swap(int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private void maxHeapify(int index,int len){
int li = (index << 1) + 1; // 左子节点索引
int ri = li + 1; // 右子节点索引
int cMax = li; // 子节点值最大索引，默认左子节点。
if(li > len) return; // 左子节点索引超出计算范围，直接返回。
if(ri <= len && arr[ri] > arr[li]) // 先判断左右子节点，哪个较大。
cMax = ri;
if(arr[cMax] > arr[index]){
swap(cMax, index); // 如果父节点被子节点调换，
maxHeapify(cMax, len); // 则需要继续判断换下后的父节点是否符合堆的特性。
}
}
public static void main(String[] args) {
int[] array1=new int[Max];
int i;
for(i=0;i<Max;i++){
array1[i]=(int)(100+Math.random()*100);//产生随机数组
}
new heapSort_day6(array1).sort();
System.out.println(Arrays.toString(array1));
}
}