package sort;

/**

* 堆排序

* 堆就是完全二叉树，分为最大堆和最小堆，最大堆要求节点的元素都要不小于其孩子（最小堆要求节点元素都不大于其左右孩子），对左右孩子的大小关系不做要求

* 所以处于最大堆的根节点的元素一定是这个堆中的最大值。堆排序算法就是抓住了堆的这一特点，每次都取堆顶的元素，将其放在序列最后面，然后将剩余的元素重新调整为最大堆，依次类推，最终得到排序的序列

* <p>

* 1、将初始待排序关键字序列(R1,R2….Rn)构造成最大堆，此堆为初始的无序区

* 2、将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]

* 3、由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。

* 不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成

*/

public class HeapSort {

public static void main(String[] args) {

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

int N = a.length;

for (int k = N / 2; k >= 1; k--) { //for循环用来构造堆，最终生成最大堆

sink(a, k, N);

}

while (N > 1) { //循环排序无序区

exch(a, 1, N--); //堆顶a[1]与堆的最后一个元素a[N]交换位置，并且去掉最后一个元素到有序区，减小新堆

sink(a, 1, N); //重新生成为最大堆

}

for (int i : a) {

System.out.print(i + " ");

}

}

/**

* 从上至下堆有序化

*/

private static void sink(int[] a, int k, int N) {

while (2 * k <= N) {

int j = 2 * k;

if (j < N && a[j] < a[j + 1]) { //j<n保证j+1不越界，a[j]和a[j+1]是a[k]的左右子节点，这里是为了选取两个子节点较大的一个，a[j]大取a[j],a[j]小取a[j++]>= a[j]) { //如果父节点大于等于值大的子节点，堆有序，终止循环

break;

}

if (a[k] >= a[j]) { //如果父节点大于等于值大的子节点，堆有序，终止循环

break;

}

exch(a, k, j); //交换值大的子节点和父节点的值，达到堆有序

k = j; //子节点，作为下一个循环的父节点，继续下沉

}

}

/**

* 交换两个元素

*/

private static void exch(int[] a, int i, int j) {

int temp = a[i];

a[i] = a[j];

a[j] = temp;

}

}