《算法导论》笔记---第6章 堆排序

/**
 * 
 * @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();
    }

}