using System;

public class Program

{

    public static void Main()

    {

        var heap = new Heap(5);

        heap.Insert(20);

        heap.Insert(22);

        heap.Insert(14);

        heap.Insert(23);

        heap.Insert(5);

        heap.Print();

        Console.WriteLine(Math.Log(5));

        var numArray = new int[5];

        var numArrayAsc = new int[5];

        //Sorting array with a heap in desc order

        //for (var i =0; i < numArray.Length; i++) {

        //  numArray[i] = heap.Remove();    

        //}

        for (var i = numArrayAsc.Length -1; i >= 0; i--) {

            numArrayAsc[i] = heap.Remove(); 

        }

        //foreach (var num in numArray) {

        //  Console.WriteLine($"Num Array - {num}") ;

        //}

        foreach (var num in numArrayAsc) {

            Console.WriteLine($"Num Array Asc - {num}");    

        }

    }

    public class Heap {

        private int[] items;

        public int Count;

        public Heap(int size) {

            items = new int[size];  

        }

        public void Insert(int num) {           

            if (IsFull()) 

                throw new InvalidOperationException();

​

            items[Count++] = num;

            BubbleUp();

        }

        public int Remove() {

            if (IsEmpty()) 

                throw new InvalidOperationException();

            var root = items[0];

            items[0] = items[--Count];

            BubbleDown();

            return root;

        }

        public bool IsEmpty() {

            return Count == 0;  

        }

        private int GetLargerChildIndex(int index) {

            if (!HasLeftChild(index))

                return index;

            if (!HasRightChild(index))

                return LeftChildIndex(index);

            return 

                    LeftChild(index) > RightChild(index) ?

                        LeftChildIndex(index) :

                        RightChildIndex(index); 

        }

        private bool HasLeftChild(int index) {

            return LeftChildIndex(index) <= Count;  

        }

        private bool HasRightChild(int index) {

            return RightChildIndex(index) <= Count; 

        }

        private bool IsValidParent(int index) {

            if (!HasLeftChild(index))

                return true;

            var isValid = items[index] >= LeftChild(index);

            if (HasRightChild(index))

                isValid &= items[index] >= RightChild(index);

            return isValid;

        }

        private int RightChild(int index) {

            return items[RightChildIndex(index)];   

        }

        private int LeftChild(int index) {

            return items[LeftChildIndex(index)];    

        }

        private int LeftChildIndex(int index) {

            return (index * 2) + 1; 

        }

        private int RightChildIndex(int index) {

            return (index * 2) + 2; 

        }

        private void BubbleUp() {

            var newItemIndex = Count - 1;

            while (newItemIndex > 0 && items[newItemIndex] > items[GetParentIndex(newItemIndex)]) {

                Swap(newItemIndex, GetParentIndex(newItemIndex));

                newItemIndex = GetParentIndex(newItemIndex);

            }

        }

        private void BubbleDown() {

            var index = 0;

            while (!IsValidParent(index) && index <= Count) {

                var largerChildIndex = GetLargerChildIndex(index);

                Swap(index, largerChildIndex);

                index = largerChildIndex;

            }

        }

        public bool IsFull() {

            return Count == items.Length;   

        }

        private int GetParentIndex(int index) {

            return (index - 1) / 2; 

        }

        private void Swap(int firstIndex, int secondIndex) {

            var temp = items[firstIndex];

            items[firstIndex] = items[secondIndex];

            items[secondIndex] = temp;

        }

        public void Print() {

            foreach (var item in items) {

                Console.WriteLine(item);    

            }

        }

    }

}