package sort;

//堆排序

/**

* (1)堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；

* 或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

* (2)PriorityQueue通过二叉小顶堆实现，可以用一棵完全二叉树表示

* (3)poll()获取并删除队首元素

* (4)peek()获取但不删除队首元素

*/

public class StackSort {

public void sort(Comparable[] a) {

int N = a.length;

//构造有序堆,只需扫描数组中一半元素

for (int i = N/2-1; i < 0; i++) {

sink(a, i ,N);

}

//将有序堆从大到小输出

N = N-1;

while (N >= 0) {

exch(a, 0, N--);

sink(a, 0, N);

}

}

private void sink(Comparable[] a, int i,int N) {

while (2*i+1 <= N-1) {

int j = 2*i+1;

if (j < N-1 && a[j].compareTo(a[j+1]) < 0) j++;

if (a[j].compareTo(a[i]) > 0) break;

exch(a, i, j);

i = j;

}

}

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

Comparable temp = a[i];

a[i] = a[j];

a[j] = temp;

}

}