public class Heap {

    public static int[] array = new int[10];
    public static int heapSize = 10;

    public static void main(String[] args) {

        array[0] = 4;
        array[1] = 1;
        array[2] = 3;
        array[3] = 2;
        array[4] = 16;
        array[5] = 9;
        array[6] = 10;
        array[7] = 14;
        array[8] = 8;
        array[9] = 7;

        long startingTime = System.nanoTime();
        SortHeapAssending();
        long endingTime = System.nanoTime();

        heapSize = 10;
        for (int j = 0; j < heapSize; j++) {
            System.out.println(array[j]);
        }

        System.out.println("Heap Execution Time " + (endingTime - startingTime) + " nano seconds");
    }

    public static void SortHeapAssending()
    {
        BuildMaxHeap(array);

        for (int i = (heapSize-1); i>=1; i--)
        {
            Swap(array,0,i);
            heapSize = heapSize - 1;
            MaxHeapify(array,0);
        }
    }

    public static void BuildMaxHeap(int[] array)
    {
         for (int i = (heapSize-1)/2; i >= 0; i--)
       {
           MaxHeapify(array, i);
       }
    }
public static void MaxHeapify(int[] array, int i)
    {
        int largestIndex;
        int leftIndex = 2 * i + 1;
        int rightIndex = 2 * i + 2;
        if (leftIndex <= heapSize-1 && array[leftIndex] > array[i])
        {
            largestIndex = leftIndex;
        }
        else
        {
            largestIndex = i;
        }
        if (rightIndex <= heapSize-1 && array[rightIndex] > array[largestIndex])
        {
            largestIndex = rightIndex;
        }
        if (largestIndex != i)
        {
            Swap(array,i,largestIndex);
            MaxHeapify(array, largestIndex);
        }
    }
}