package practice;


import edu.princeton.cs.algs4.StdRandom;

public class TestMain {
    public static void main(String[] args) {
        int[] a = new int[20];
        for (int i = 0; i < a.length; i++) {
            int temp = (int)(StdRandom.random()*100);
            a[i] = temp;
        }
        HeapSrot.sort(a);
        for (int i = 1; i < a.length; i++) { //只能从a[1]开始排
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }
}

class HeapSrot{
    public static void sort(int[] a) {
        int p = a.length;
        for (int k = p/2; k >= 1; k--) { //因为没有子元素的节点不用处理，所以只处理一半元素
            sink(a, k, p); //从下往上将所有(不包括没有子元素的节点)，节点沉一遍，整个数组则堆有序
        } //为什么不像优先队列那样插入再上浮，因为这样可以快20%~30%
        while (p > 1) { //和优先队列弹出最大元素并删除操作一样，不是删除而是将最大元素移到末尾
            exch(a, 1, --p); //将第一个移到末尾
            sink(a, 1, p); //将换上来的沉下去
        }
    }
    /*
     * 下沉
     */
    private static void sink(int[] a,int k,int p) { //将元素与子元素比较，比子元素小则和两个中较大的那个换位置
        while ((2*k + 1) < p && ((a[k] < a[2*k + 1]) || (a[k] < a[2*k]))) {            
            if (a[2*k + 1] > a[2*k]) { exch(a, k, 2*k + 1); k = 2*k + 1; }
            else                     { exch(a, k, 2*k); k = 2*k; }
        }
    }
    /*
     * 交换
     */
    private static void exch (int[] a,int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}