public class Test04 {
    /**
     * 堆是一种数据结构，一般采用完全二叉树的形式实现（堆一定是完全二叉树，完全二叉树不一定是堆，
     * 注意区分完全二叉树和排序二叉树），队列是线性表的一种，线性表属于线性结构，     树是树形结构。堆是一种线性表。   
*优先队列通常用堆来实现，而堆有两个性质，一，子节点总是不大于或者不小于父节点，二，堆总是一棵完全二叉树。
     * @param v1
     * @param w1
     * @return
     */

    public static boolean less(Comparable v1,Comparable w1){
        int v=Integer.parseInt((String)v1);
        int w=Integer.parseInt((String)w1);
        if (v<w)
            return true;
        else
            return false;
    }

    public static void exch(Comparable[] a,int i,int j){
        Comparable t =a[i];
        a[i]=a[j];
        a[j]=t;
    }
    public static void sink(Comparable[] pq,int k,int N){
        //pq数组第一个元素为null，所以数组中的索引值与元素位置对应（即堆中第一个数字索引为1而不是0）
       // int N=pq.length;
        //下面这个while循环，如果不减一（原书上未减一），那么数组有16个元素时，第八个元素小于等于16，那么迭代时会有角标越界。
        while (2*k<=N-1){
            int j=2*k;
            //堆上面的元素与下面两个元素中较大元素换位置
            if (j<=N&&less(pq[j],pq[j+1])){
                j++;
            }
            //堆上面的元素大于下面的元素则停止
            if (!less(pq[k],pq[j])){
                break;
            }
            exch(pq,k,j);
            k=j;
          //  N--;

        }
    }
    public static void sort(Comparable[]comparables){
        int N=comparables.length;
        for (int k=N/2;k>=1;k--){
        //这个for循环用于构建完全二叉树
            sink(comparables,k,N);
        }
        int M=N-1;
        while(M>3){
        //把上浮的元素排到最后，即可排序
            exch(comparables,1,M);

            M=M-1;
            sink(comparables,1,M);
        }
        exch(comparables,1,M);
    }
    public static void main(String[] args) {
        String[] a = {null,"3", "2", "4", "1", "6", "5", "10", "9", "8", "7","13","11","12","14","15"};
 
        sort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);

        }
    }
}