public class HeapSort {
/**
* 调整第i个堆元素为根结点的堆为最大堆，前提条件是i的左右孩子已经是最大堆，注意这里的i是在堆中的位置并非数组中的位置
* @param arr 堆数组
* @param i 调整第i个堆元素为根结点的堆为最大堆
* @param heapsize ：堆大小即堆中元素个数，在heapSort中会不断的把最大的元素置换出去，
* 虽然置换出去的元素仍然在数组中，但是已经不是堆中的元素
*/
static void maxHeap(int arr[],int i,int heapsize){
int largest = i;
int p = 2*i;
int q = 2*i + 1;
//由于i和heapsize都是指的元素在堆中的位置而非在数组中的位置，所以涉及到数组操作时都要减1
if(p<=heapsize&&arr[p-1]>arr[largest-1])
largest = p;
if(q<=heapsize&&arr[q-1]>arr[largest-1])
largest = q;
if(largest!=i){
int temp = arr[i-1];
arr[i-1]=arr[largest-1];
arr[largest-1]=temp;
//尽管i的左右孩子已经是最大堆，但是当前面的调整发生以后，其左右孩子就有可能不再是最大堆了，所以要重新调整成最大堆
maxHeap(arr,largest,heapsize);
}
}
/**
* 把一个无序的数组构建成最大堆
* @param arr 数组
*/
static void buildMaxHeap(int arr[]){
int length = arr.length/2;
//尽管i在数组中的位置是从length-1到0，但是这里不能设置为数组中的位置，
//因为在maxHeap中计算i的左右孩子时是乘2为左孩子，乘2加1为右孩子，
//如果按数组位置，那么这样的计算就不对了，例如根结点在数组中为0，则其左孩子为2*0=0，这就出错了
for(int i = length;i>0;i--)
maxHeap(arr,i,arr.length);
}
/**
* 最外层的排序函数
* @param arr
*/
static void heapSort(int arr[]){
//先把无序的数组建成最大堆
buildMaxHeap(arr);
//把堆顶元素输出，把堆最后一个元素放到堆顶，这样输出的最大元素就不在堆中了，但是仍在数组中，所以堆大小要减1
for(int i = arr.length;i>1;i--){
int temp = arr[0];
arr[0]=arr[i-1];
arr[i-1]=temp;
maxHeap(arr,1,i-1);
}
}
public static void main(String[] args) {
int arr[] = {1,3,4,2,7,8,9,10,14,16};
heapSort(arr);
for(int i =0;i<arr.length;i++)
System.out.println(arr[i]);
}
}
