private void heapAdd(int arr[], int end){
        int i = end;
        while(i > 0){
            if(arr[i] > arr[(i-1)/2]){
                swap(arr, i, (i-1)/2);
                i = (i - 1)/2;
            }else{
                break;
            }
        }
    }
Date 04/03/2015
@author tusroy

Heap Sort
Given an array sort it using heap sort

Solution :
First convert the original array to create the heap out of the array
Then move the max element to last position and do heapify to recreate the heap
with rest of the array element. Repeat this process

Time complexity
O(nlogn)

Test cases
Null array
1 element array
2 element array
sorted array
reverse sorted array
src/com/interview/sort/HeapSort.java