/**
 *  Average case performance: O(nlogn)
 *  Best case performance:    O(nlogn)
 *  Worst case performance:   O(nlogn)
 */
public class HeapSort {
    
    /**
     * @param a Array of integers which are sorted when returns.
     */
    public static void sort(int[] a){
        
        /* Insertion onto heap */
        for(int k=0; k<a.length; k++){
            int n = k;
            while(n>0){
                int p = (n-1)/2; // parent
                if(a[n]>a[p]){
                    swap(a, n, p);
                    n = p;
                }else{
                    break;
                }
            }
        }
        
        /* Removal from heap */
        for(int k=a.length-1; k>0; k--){
            swap(a, 0, k);
            maxHeap(a, k, 0);
        }
    }
    
    /**
     * @param a Array of integers
     * @param size The heapsize
     * @param p The starting point/parent to heapify
     */
    private static void maxHeap(int[] a, int size, int p)
    {
        int left  = 2*p + 1;
        int right = left + 1;
        
        // leaf node
        if(left>=size)
            return;
        // node with only left child
        if(right>=size){
            if(a[left]>a[p]){
                swap(a, left, p);
            }
            return;
        }
        
        // find the largest among node, left child and right child.
        int largest = p;
        if(a[left]>a[p])
            largest = left;
        if(a[right]>a[largest])
            largest = right;
        
        if(largest!=p){
            swap(a, p, largest);
            maxHeap(a, size, largest);
        }
    }
    
    private static void swap(int[] a, int j, int k) {
        int temp = a[j];
        a[j] = a[k];
        a[k] = temp;
    }

}