using System;

public class Program

{

    public static void Main()

    {

        int[] nums = new int[] { 87, 16, 69 , 49, 70, 1, 3 ,4, 5 ,95};

        HeapSort(nums);

        Print(nums);

        Console.WriteLine("Hello World");

    }

    public static void HeapSort(int[] n)

    {

        int length = n.Length;

        for(int i = length/2 -1; i > 0 - 1; i--)

        {

            Heapify(n, length, i);

        }

        for (int i=length-1; i>=0; i--)

        {  

            // Move current root to end

            Swap(n , 0, i);

            // call max heapify on the reduced heap

            Heapify(n, i, 0);

        }

    }

    private static void Heapify(int[] n, int endIndex, int currentIndex)

    {

        int largest = currentIndex;  // Initialize largest as root

        int l = 2*currentIndex + 1;  // left = 2*i + 1

        int r = 2*currentIndex + 2;  // right = 2*i + 2

        // If left child is larger than root

        if (l < endIndex && n[l] > n[largest])

            largest = l;

        // If right child is larger than largest so far

        if (r < endIndex && n[r] > n[largest])

            largest = r;

        // If largest is not root

        if (largest != currentIndex)

        {

            Swap(n, currentIndex, largest);

            // Recursively heapify the affected sub-tree

            Heapify(n, endIndex, largest);

        }

    }

    public static void Swap(int[] nums, int leftItemIndex, int rightItemIndex)

    {

        int tempInnerValue = nums[leftItemIndex];

        nums[leftItemIndex] = nums[rightItemIndex];

        nums[rightItemIndex] = tempInnerValue;

    }

    private static void Print(int[] nums)

    {

        Console.WriteLine(string.Join(", ", nums));

    }

}