package lhz.algorithm.chapter.six; 
/** 
 * “堆排序”，《算法導論》6.4章節(jié) 
 * 利用之前實現(xiàn)的構(gòu)建MaxHeap和MaxHeapify算法完成排序。 
 * 偽代碼： 
 * HEAPSORT(A) 
 * 1 BUILD-MAX-HEAP(A) 
 * 2 for i ← length[A] downto 2 
 * 3 do exchange A[1] ? A[i] 
 * 4 heap-size[A] ← heap-size[A] - 1 
 * 5 MAX-HEAPIFY(A, 1) 
 * @author lihzh(苦逼coder)  * 本文地址：http://mushiqianmeng.blog.51cto.com/3970029/738164  */ 
public class HeapSort { 
     
    private static int[] input = new int[] {16, 14, 10, 8, 7, 9, 3, 2, 4, 1}; 
 
    public static void main(String[] args) { 
        //堆排序 
        heapSort(); 
        //打印數(shù)組 
        printArray(); 
    } 
     
    /** 
     * 堆排序，《算法導論》原文摘要： 
     * The heapsort algorithm starts by using BUILD-MAX-HEAP to build a max-heap on the input 
     * array A[1  n], where n = length[A]. Since the maximum element of the array is stored at the 
     * root A[1], it can be put into its correct final position by exchanging it with A[n].  
     * If we now "discard" node n from the heap (by decrementing heap-size[A]), we observe that  
     * A[1  (n -1)] can easily be made into a max-heap. The children of the root remain max-heaps,  
     * but the new root element may violate the max-heap property. All that is needed to restore  
     * the maxheap property, however, is one call to MAX-HEAPIFY(A, 1), which leaves a max-heap  
     * in A[1 (n - 1)]. The heapsort algorithm then repeats this process for the max-heap of size  
     * n - 1 down to a heap of size 2. 
     * 復雜度： 
     * 由之前分析可知，buildMaxHeap復雜度為O(n lg n)，運行一次。 
     * maxHeapify的復雜度為O(lg n)，運行n-1次。 
     * 綜上，復雜度為O(n lg n)。 
     */ 
    private static void heapSort() { 
        int length = input.length; 
        //構(gòu)造max-heap 
        buildMaxHeap(input, length);//交換位置 
        for (int i = length - 1; i > 0; i--) { 
            int temp = input[i]; 
            input[i] = input[0]; 
            input[0] = temp; 
            maxHeapify(input, 1, i); 
        } 
    } 
 
    private static void buildMaxHeap(int[] array, int heapSize) { 
        for (int i = heapSize / 2; i > 0; i--) { 
            maxHeapify(array, i, heapSize); 
        } 
    } 
     
    private static void maxHeapify(int[] array, int index, int heapSize) { 
        int l = index * 2; 
        int r = l + 1; 
        int largest; 
        //如果左葉子節(jié)點索引小于堆大小，比較當前值和左葉子節(jié)點的值，取值大的索引值 
        if (l <= heapSize && array[l-1] > array[index-1]) { 
            largest = l; 
        } else { 
            largest = index; 
        } 
        //如果右葉子節(jié)點索引小于堆大小，比較右葉子節(jié)點和之前比較得出的較大值，取大的索引值 
        if (r <= heapSize && array[r-1] > array[largest-1]) { 
            largest = r; 
        } 
        //交換位置，并繼續(xù)遞歸調(diào)用該方法調(diào)整位置。 
        if (largest != index) { 
            int temp = array[index-1]; 
            array[index-1] = array[largest-1]; 
            array[largest-1] = temp; 
            maxHeapify(array, largest, heapSize); 
        } 
    } 
     
    private static void printArray() { 
        for (int i : input) { 
            System.out.print(i + " "); 
        } 
    } 
}