package algorith;
public class Heap {
/**
* @param args
* 最大堆排序
*/
public static void main(String[] args) {
Heap h = new Heap ();
int[] a ={3,4,5,2,1,6,7};
h.initialization(a);
for(int b :a){
System.out.print(b+" ");
}
System.out.println();
h.sort(a);
for(int b :a){
System.out.print(b+" ");
}
}
public void initialization(int[] array){
int len = array.length;
for(int i =len/2-1 ;i>=0;i--){
maxHeap(array,i,len);
}
}
public static void maxHeap(int[] array , int i ,int length){
int index = i ;
if((2*i+1 <=length-1 )&&(array[2*i+1]>array[i])){
index = 2*i+1;
}
if((2*i+2 <=length-1 )&&(array[2*i+2]>array[index])){
index = 2*i+2;
}
if(index != i){
swap(array,index,i);
maxHeap(array,index,length);
}
}
//把第一个值与最后一个交换,排除最后一个,对其他的树操作!
public void sort(int[] array){
int len = array.length;
for(int i = array.length-1; i>=0;i--){
swap(array,0,i);
len-=1;
maxHeap(array,0,len);
}
}
public static void swap(int[] array , int i , int j){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请
点击举报。