using System;

public class Program

{

    public static void Main()

    {

          int[] A = {3, 55, 77, 1, 4, 88, 2, 4, 5};

          HeapSort(A, 0, A.Length-1);

        for (int i = 0; i < A.Length ; i++)

        Console.WriteLine(A[i]);

    }

    static void HeapSort(int[] list, int dummy1, int max) {

        for (int i = max/2; i >= 0; i--){

            FixHeap(list, i, list[i], max);

        }

        for (int i = max-2; i >= 0; i--) {

           Swap(list, i+1, 0);

            FixHeap(list, 1, list[1], i-1); 

        }

    }

    static void FixHeap(int[] list, int root, int key, int bound){

        int vacant = root;

        while (2 * vacant <= bound){

            int largerChild = 2 * vacant;

            if ((largerChild < bound) && (list[largerChild+1] > list[largerChild])){

                largerChild = largerChild +1;

            } 

            if (key > list[largerChild]){

                break;

            }

            else{

                list[vacant] = list[largerChild];

                vacant = largerChild;

            }

        }

        list[vacant] = key;

    }

​

    static void Swap(int[] list, int i, int j)

    {

        int temp = list[i]; // swap elements

        list[i] = list[j];

        list[j] = temp;

    }

}