public class HeapSort {

public static void main(String[] args) {

int[] num = {3,1,5,7,2,4,9,6,10,8};

System.out.println("排序前的数据：");

for(int i = 0; i < num.length; i++){

System.out.print(num[i] + " ");

}

System.out.println();

HeapSort.heapSort(num, num.length);

System.out.println("排序后的数据：");

for(int i = 0; i < num.length; i++){

System.out.print(num[i] + " ");

}

System.out.println();

}

private static void heapSort(int[] num, int len){

/** 初始化堆

* 初始堆进行调整

* 将num[0..length-1]建成堆

* 调整完之后第一个元素是序列的最小的元素

*/

for(int i = (len - 1) / 2; i >= 0; i--){ //非叶节点最大序号值为size/2,size为数组元素最大的下标

headAdjust(num, i, len);

}

//从最后一个元素开始对序列进行调整

for (int i = len - 1; i > 0; i--)

{

//交换堆顶元素H[0]和堆中最后一个元素

int temp = num[i];

num[i] = num[0];

num[0] = temp;

//每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整

headAdjust(num,0,i);

}

}

/**

* 已知H[s…m]除了H[s] 外均满足堆的定义

* 调整H[s],使其成为大顶堆.即将对第s个结点为根的子树筛选,

*

* @param H是待调整的堆数组

* @param s是待调整的数组元素的位置

* @param length是数组的长度

*

*/

public static void headAdjust(int[] H, int s, int length){

int tmp = H[s];

int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)

while (child < length) {

if(child+1 <length && H[child]>H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)

++child ;

}

if(H[s]>H[child]) { // 如果较大的子结点大于父结点

H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点

s = child; // 重新设置s ,即待调整的下一个结点的位置

child = 2*s+1;

} else { // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出

break;

}

H[s] = tmp; // 当前待调整的结点放到比其大的孩子结点位置上

}

}

}