using System;

 using System.Collections.Generic;

 using System.Linq;

 using System.Text;

 using System.Threading.Tasks;

 namespace ConsolePractice

 {

     public class Node

     {

         public int data;

         public Node(int key)

         {

             data = key;

         }

     }

     class Heap

     {

         Node[] heapArray = null;

         private int maxSize = ;

         private int currSize = ;

         public Heap(int maxSize)

         {

             this.maxSize = maxSize;

             heapArray = new Node[maxSize];

         }

         public bool InsertAt(int pos, Node nd)

         {

             heapArray[pos] = nd;

             return true;

         }

         public void ShowArray()

         {

             for (int i = ; i < maxSize; i++)

             {

                 if (heapArray[i] != null)

                     Console.Write(heapArray[i].data + " ");

             }

             Console.WriteLine();

         }

         public void ShiftUp(int index)

         {

             int parent = (index - ) / ;

             Node bottom = heapArray[index];

             while ((index > ) && (heapArray[parent].data < bottom.data))

             {

                 heapArray[index] = heapArray[parent];

                 index = parent;

                 parent = (parent - ) / ;

             }

             heapArray[index] = bottom;

         }

         public bool Insert(int key)

         {

             if (currSize == maxSize)

                 return false;

             heapArray[currSize] = new Node(key);

             currSize++;

             return true;

         }

         public Node Remove()

         {

             Node root = heapArray[];

             currSize--;

             heapArray[] = heapArray[currSize];

             ShiftDown();

             return root;

         }

         public void ShiftDown(int index)

         {

             int largerChild;

             Node top = heapArray[index];

             while (index < (int)(currSize / ))

             {

                 int leftChild =  * index + ;

                 int rightChild = leftChild + ;

                 if ((rightChild < currSize) && heapArray[leftChild].data < heapArray[rightChild].data)

                     largerChild = rightChild;

                 else

                     largerChild = leftChild;

                 if (top.data >= heapArray[largerChild].data)

                     break;

                 heapArray[index] = heapArray[largerChild];

                 index = largerChild;

             }

             heapArray[index] = top;

         }

     }

     class C_shape

     {

         static void Main()

         {

             const int SIZE = ;

             Heap aHeap = new Heap(SIZE);

             Random RandomClass = new Random();

             for (int i = ; i < SIZE; i++)

             {

                 int rn = RandomClass.Next(, );

                 aHeap.Insert(rn);

             }

             Console.WriteLine("Random:");

             aHeap.ShowArray();

             Console.WriteLine("Heap:");

             for (int i = (int)SIZE /  - ; i >= ; i--)

             {

                 aHeap.ShiftDown(i);

             }

             aHeap.ShowArray();

             Console.WriteLine("Sorted:");

             for (int i = SIZE - ; i >= ; i--)

             {

                 Node bigNode = aHeap.Remove();

                 aHeap.InsertAt(i, bigNode);

             }

             aHeap.ShowArray();

             Console.ReadKey();

         }

     }

 }