堆排序（和堆实现的优先队列一起 ）

思路

取堆的一半后，分解最小子堆 （使用sink()，如果子结点有比父结点大的值的话 取较大子结点和父结点交换，满足堆的性质），然后递归往上取父结点（父结点和其子结点使用sink()，使满足堆的性质），这样一直到根结点，这样就构造了一个堆
交换根结点和最后一个结点，堆的规模-1，然后新的根结点下沉（重新满足堆，根结点是当前堆的最大值）

注意

堆的第一个元素为空 N = this.a.length - 1;

public class HeapSort<K extends Comparable<K>> {
    public K[] a;
    //N 是去掉第一个元素之后  元素的个数
    int N ;
    public HeapSort (){
        
    }
    @SuppressWarnings("unchecked")
    public HeapSort (K[] a){
        this.a = (K[]) new Comparable[a.length + 1];
        for (int i = 0; i < a.length; i++) {
            this.a[i+1] = a[i];
        }
        N = this.a.length - 1;
    }
    public void sort(){
//      int N = a.length-1;
        for(int k = N/2; k > 0; k--){
            sink( k, N);
            
        }
        while(N > 0){
            System.out.println(N);
            exch( 1, N--);
            sink( 1, N);
        }
        System.out.println("");
    }

    private void exch(int i, int j) {
        K tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    private boolean less(int j, int i) {
        
        return a[j].compareTo(a[i]) < 0 ? true : false;
    }
    private void sink(int k, int n) {
        while(2 * k <= n){
            int x = 2 * k;
            if(x < n && less(x, x + 1)){
                x++;
            }
            if(!less(k, x)){
                break;
            }
            exch(x, k);
            k = x;
        }
    }
}

    @Test
    public void test01(){
        Integer[] a = {5, 6, 2, 3, 1, 4};
        HeapSort<Integer> heapSort = new HeapSort<Integer>(a);
        heapSort.sort();
        for (int i = 0; i < 6; i++) {
        }
    
    }