using System;

namespace Heapsort
{
    class Program
    {
        public static void Main (string[] args)
        {

            int i;
            int[] arrOne = {503,087,512,061,908,170,897,275,653,426,154,509,612,677,765,703};
            int[] arrTwo = {908,897,765,703,677,653,612,512,509,503,426,275,170,154,087,061};
            int[] arrThree = {300};
            int[] arrFour = {0,1,0,0,1,1,1,0,1,0};
            int n = 0;
            string c = String.Empty;

            // the application runs until the user agrees to quit at the end of a sorting run
            do
            {
                // displays the 4 arrrays
                Console.WriteLine ("Assignment: Given are 4 different arrays; You have the choice which one you want to sort.");
                Console.WriteLine ("\n1. Knuths entry sequence:\n   503,087,512,061,908,170,897,275,653,426,154,509,612,677,765,703");
                Console.WriteLine ("\n2. Knuths entry sequence descended:\n   908,897,765,703,677,653,612,512,509,503,426,275,170,154,087,061");
                Console.WriteLine ("\n3. Just one number:\n   300");
                Console.WriteLine ("\n4. A set of 0 and 1:\n   0,1,0,0,1,1,1,0,1,0");
                Console.WriteLine ("\n Which array do you want to sort?");
                n = Convert.ToInt32(Console.ReadLine());
                Console.Clear();

                GlobalVar.CountVal = 0;

                switch (n)
                {
                case 1:
                    for (i = arrOne.Length; i > 1; i--)
                    {
                        Program.HeapSort(arrOne, i - 1);
                    }
                    DisplayArray(arrOne);
                    break;
                case 2:
                    for (i = arrTwo.Length; i > 1; i--)
                    {
                        Program.HeapSort(arrTwo, i - 1);
                    }
                    DisplayArray(arrTwo);
                    break;
                case 3:
                    for (i = arrThree.Length; i > 1; i--)
                    {
                        Program.HeapSort(arrThree, i - 1);
                    }
                    DisplayArray(arrThree);
                    break;
                case 4:
                    for (i = arrFour.Length; i > 1; i--)
                    {
                        Program.HeapSort(arrFour, i - 1);
                    }
                    DisplayArray(arrFour);
                    break;
                default:
                    Console.WriteLine ("\n Array not exist!");
                    break;
                }

                Console.WriteLine("\nThe case needed " + GlobalVar.CountVal + " comparisons!");
                Console.WriteLine("\nDo you want to quit the application? (y/n) ");
                c = Console.ReadLine();
                Console.Clear();

            }
            while (c != "y");


        }

        // displays the array
        public static void DisplayArray(int[] arr)
        {
            Console.WriteLine("\nSorted Array!\n");

            for (int i = 0; i < arr.Length; i++)
                Console.WriteLine ("   " + arr[i]);
        }

        // sorts the array with the heapsort algorithm
        // first the root node gets selected and then the right and left child gets selected
        // if value of child is greater than its parent node then they get swapped
        // after creating heap condition the algo removes the largest element and places it in the new array of sorted elements
        public static void HeapSort(int[] array, int arr_ubound)
        {
            int i, j;
            int lChild, rChild, pNode, root, temp;

            root = (arr_ubound - 1) / 2;

            // for debugging
            //Console.WriteLine ("root " + root);
            //Console.WriteLine ("arr_ubound " + arr_ubound);

            for (j = root; j >= 0; j--)
            {
                for (i = root; i >= 0; i--)
                {
                    GlobalVar.CountVal += 1;
                    lChild = (2*i)+1;
                    rChild = (2*i)+2;

                    if ((lChild <= arr_ubound) && (rChild <= arr_ubound))
                    {
                        if (array[rChild] >= array[lChild])
                            pNode = rChild;
                        else
                            pNode = lChild;
                    }
                    else
                    {
                        if (rChild > arr_ubound)
                            pNode = lChild;
                        else
                            pNode = rChild;
                    }

                    if (array[i] < array[pNode])
                    {
                        temp = array[i];
                        array[i] = array[pNode];
                        array[pNode] = temp;
                    }
                }
            }

            temp = array[0];
            array[0] = array[arr_ubound];
            array[arr_ubound] = temp;
            return;
        }
    }
}

// using a global variable to count the comparisons for each case
public static class GlobalVar
{
    static int _countVal;

    public static int CountVal
    {
        get{return _countVal;}
        set{_countVal = value;}
    }
}