/** *  * @author gyb * 《算法导论（第二版）》--第六章 堆排序 *  * maxHeapify(int[] a,i) *     将指定结点i的子树成为最大堆 * 书中伪代码: * MAX-HEAPIFY(A, i)   *     l ← LEFT(i)   *     r ← RIGHT(i)   *     if l ≤ heap-size[A] and A[l] > A[i]   *         then largest ← l   *         else largest ← i   *     if r ≤ heap-size[A] and A[r] > A[largest]   *         then largest ← r   *     if largest ≠ i   *         then exchange A[i] ↔ A[largest] 10  *             MAX-HEAPIFY(A, largest)  * 时间复杂度 *     因为    ：T (n) ≤ T(2n/3) + Θ(1)  *     所以    ：T (n) = O(lgn)  *  * buildMaxHeap(int[] a) *     自底向上地用MAX-HEAPIFY将一个数组A[1..n](此处n=length[A])变成一个最大堆 * 书中伪代码： * BUILD-MAX-HEAP(A)  *     heap-size[A] ← length[A]  *     for i ← length[A]/a downto 1    (此处length[A]/2做向下取整,符号没打出来...)  *         do MAX-HEAPIFY(A, i)  * 时间复杂度 *     因为    ：O(n)次调用O(lgn)  *     所以    ：T(n) = O(nlgn) *     但是更加紧确值为： O(n) *     具体原因看书。 *  */public class HeapTest {    //    private static int[] a = new int[] { 16,4,10,14,7,9,3,2,8,1 }; //    private static int[] a = new int[] { 4,1,3,2,16,9,10,14,8,7 };     private static int[] a = new int[] { 5,3,17,10,84,19,6,22,9};         private static int heapSize = a.length;         public static void maxHeapify(int[] a, int i){        int l = i*2;        int r = l+1;        int largest;                if(l <= heapSize && a[l-1] > a[i-1]){            largest = l;                    }else{            largest = i;        }                        if(r <= heapSize && a[r-1] > a[largest-1]){            largest = r;        }                    if(i != largest){            int temp = a[i-1];             a[i-1] = a[largest-1];             a[largest-1] = temp;             maxHeapify(a,largest);        }    }    public static void buildMaxHeap(int[] a){        for(int i = a.length / 2; i > 0; i--)            maxHeapify(a, i);    }        public static void output(){        StringBuffer sb = new StringBuffer();        for (int i : a) {            sb.append(i);            sb.append(" ");        }        System.out.println(sb.toString());    }    /**     * @param args     */    public static void main(String[] args) {        // TODO Auto-generated method stub        maxHeapify(a,4);//        buildMaxHeap(a);        output();    }}