思路

取堆的一半后，分解最小子堆 （使用sink()，如果子結(jié)點(diǎn)有比父結(jié)點(diǎn)大的值的話 取較大子結(jié)點(diǎn)和父結(jié)點(diǎn)交換，滿足堆的性質(zhì)），然后遞歸往上取父結(jié)點(diǎn)（父結(jié)點(diǎn)和其子結(jié)點(diǎn)使用sink()，使?jié)M足堆的性質(zhì)），這樣一直到根結(jié)點(diǎn)，這樣就構(gòu)造了一個(gè)堆
交換根結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)，堆的規(guī)模-1，然后新的根結(jié)點(diǎn)下沉（重新滿足堆，根結(jié)點(diǎn)是當(dāng)前堆的最大值）

注意

堆的第一個(gè)元素為空 N = this.a.length - 1;

public class HeapSort<K extends Comparable<K>> {
    public K[] a;
    //N 是去掉第一個(gè)元素之后  元素的個(gè)數(shù)
    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++) {
        }
    
    }