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;
    }
}