using System;
using System.Collections.Generic;
using System.Text;

namespace Sorting
{
    /// <summary>
    /// Binary heap
    /// </summary>
    public class DateHeap
    {
        DateTime[] data;
        int length;

        public DateHeap(DateTime[] input, int length)
        {
            this.data = input;
            this.length = length;
        }

        public void DecrementLength()
        {
            length--;
        }

        #region Properties
        public DateTime this[int index]
        {
            get
            {
                return data[index - 1];
            }
            private set
            {
                data[index - 1] = value;
            }
        }
        public DateTime[] Data
        {
            get
            {
                return data;
            }
        }
        public int Length
        {
            get
            {
                return length;
            }
        }
        public int NumberOfLeaves
        {
            get
            {
                return (int)Math.Ceiling(this.Length / 2.0);
            }
        }
        public int LastInternalNodeIndex
        {
            get
            {
                return (int)Math.Floor(this.Length / 2.0);
            }
        }

        public int Height
        {
            get
            {
                return (int)Math.Floor(Math.Log(this.Length, 2));
            }
        }
        #endregion

        public int ParentIndex(int index)
        {
            return (int)Math.Floor(index / 2.0);
        }

        public int LeftChildIndex(int index)
        {
            return (index * 2);
        }

        public int RightChildIndex(int index)
        {
            int retval = (index * 2) + 1;
            if (retval <= length)
                return retval;
            else
                return -1;
        }

        public bool HasRightChild(int index)
        {
            return RightChildIndex(index) > -1 ? true : false;
        }

        public DateTime RightChildValue(int index)
        {
            return this[RightChildIndex(index)];
        }

        public DateTime LeftChildValue(int index)
        {
            return this[LeftChildIndex(index)];
        }

        void SwapValues(int indexa, int indexb)
        {
            DateTime temp = this[indexa];
            this[indexa] = this[indexb];
            this[indexb] = temp;
        }

        /// <summary>
        /// Fix Heap Recursive
        /// </summary>
        /// <param name="bh"></param>
        /// <param name="node"></param>
        static void FixHeapMax(ref DateHeap bh, int node)
        {

            DateTime nodevalue = bh[node];

            //see if node has a right child
            if (!bh.HasRightChild(node))
            {
                //check if heap property is maintained
                if (nodevalue < bh.LeftChildValue(node))
                    bh.SwapValues(node, bh.LeftChildIndex(node));

            }
            else
            {
                DateTime leftvalue = bh.LeftChildValue(node);
                DateTime rightvalue = bh.RightChildValue(node);
                if (leftvalue > rightvalue)
                {
                    if (leftvalue > nodevalue)
                        bh.SwapValues(node, bh.LeftChildIndex(node));
                }
                else
                {
                    if (rightvalue > nodevalue)
                        bh.SwapValues(node, bh.RightChildIndex(node));
                }
            }

            if (node > 1)
            {
                FixHeapMax(ref bh, node - 1);
            }

        }

        /// <summary>
        /// Fix Heap Recursive
        /// </summary>
        /// <param name="bh"></param>
        /// <param name="node"></param>
        static void FixHeapMin(ref DateHeap bh, int node)
        {

            DateTime nodevalue = bh[node];

            //see if node has a right child
            if (!bh.HasRightChild(node))
            {
                //check if heap property is maintained
                if (nodevalue > bh.LeftChildValue(node))
                    bh.SwapValues(node, bh.LeftChildIndex(node));

            }
            else
            {
                DateTime leftvalue = bh.LeftChildValue(node);
                DateTime rightvalue = bh.RightChildValue(node);
                if (leftvalue < rightvalue)
                {
                    if (leftvalue < nodevalue)
                        bh.SwapValues(node, bh.LeftChildIndex(node));
                }
                else
                {
                    if (rightvalue < nodevalue)
                        bh.SwapValues(node, bh.RightChildIndex(node));
                }
            }

            if (node > 1)
            {
                FixHeapMin(ref bh, node - 1);
            }

        }

        /// <summary>
        /// Heap sort Recursive
        /// </summary>
        /// <param name="bh"></param>
        public static void HeapSortMax(ref DateHeap bh)
        {
            int node = bh.LastInternalNodeIndex;
            FixHeapMax(ref bh, node);
            bh.SwapValues(1, bh.Length);
            bh.DecrementLength();
            if (bh.Length > 1)
                HeapSortMax(ref bh);

        }


        /// <summary>
        /// Heap sort Recursive
        /// </summary>
        /// <param name="bh"></param>
        public static void HeapSortMin(ref DateHeap bh)
        {
            int node = bh.LastInternalNodeIndex;
            FixHeapMin(ref bh, node);
            bh.SwapValues(1, bh.Length);
            bh.DecrementLength();
            if (bh.Length > 1)
                HeapSortMin(ref bh);

        }
    }
}


