BinaryHeap

gistfile1.txt

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace Collections
{
    /// <summary>
    ///     A binary heap.
    /// </summary>
    /// <typeparam name="T">    Generic type parameter. </typeparam>
    public class BinaryHeap <T> : ICollection, IReadOnlyCollection<T> where T : IComparable<T>
    {
        private int _numberOfNodes;
        private T[] _binaryHeap;

        private BinaryHeapOrder _order;

        /// <summary>
        ///     Gets the number of items.
        /// </summary>
        public int Count => _numberOfNodes - 1;

        /// <summary>
        /// Gets an object that can be used to synchronize access to the
        /// <see cref="T:System.Collections.ICollection" />.
        /// </summary>
        public object SyncRoot => _binaryHeap.SyncRoot;

        /// <summary>
        /// Gets a value indicating whether this object is synchronized.
        /// </summary>
        public bool IsSynchronized => _binaryHeap.IsSynchronized;

        /// <summary>
        ///     Gets the base.
        /// </summary>
        /// <param name="numberOfElements"> Number of elements. </param>
        public BinaryHeap(BinaryHeapOrder order, int numberOfElements = 16)
        {
            _binaryHeap = new T[numberOfElements + 1];
            _numberOfNodes = 1;
            _order = order;

        }

        /// <summary>
        ///     Gets the enumerator.
        /// </summary>
        /// <returns>
        ///     The enumerator.
        /// </returns>
        public IEnumerator<T> GetEnumerator()
        {
            throw new NotSupportedException();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        /// <summary>
        ///     Copies the elements of the <see cref="T:System.Collections.ICollection" /> to an
        ///     <see cref="T:System.Array" />, starting at a particular <see cref="T:System.Array" /> index.
        /// </summary>
        /// <exception cref="T:System.ArgumentNullException">       . </exception>
        /// <exception cref="T:System.ArgumentOutOfRangeException"> . </exception>
        /// <exception cref="T:System.ArgumentException">           . </exception>
        /// <param name="array">
        ///     The one-dimensional <see cref="T:System.Array" /> that is the
        ///     destination of the elements copied from
        ///     <see cref="T:System.Collections.ICollection" />. The
        ///     <see cref="T:System.Array" /> must have zero-based indexing.
        /// </param>
        /// <param name="index">
        ///     The zero-based index in <paramref name="array" /> at which copying
        ///     begins.
        /// </param>
        public void CopyTo(Array array, int index)
        {
            throw new NotSupportedException();
        }

        /// <summary>
        ///     Clears this object to its blank/initial state.
        /// </summary>
        public void Clear()
        {
            _numberOfNodes = 1;
        }

        /// <summary>
        /// Query if this object contains the given node.
        /// </summary>
        ///
        /// <param name="node"> The node to push. </param>
        ///
        /// <returns>
        /// True if the object is in this collection, false if not.
        /// </returns>
        public bool Contains(T node)
        {
            var newHeap = new T[_numberOfNodes - 1];
            Array.Copy(_binaryHeap, 1, newHeap, 0, _numberOfNodes - 1);
            return newHeap.Contains(node);
        }

        /// <summary>
        ///     Pushes an object onto this stack.
        /// </summary>
        /// <param name="node"> The node to push. </param>
        public void Push(T node)
        {
            if (node == null)
            {
                return;
            }

            if (_numberOfNodes == _binaryHeap.Length)
            {
                var newHeap = new T[_binaryHeap.Length * 2];
                Array.Copy(_binaryHeap, newHeap, _binaryHeap.Length);
                _binaryHeap = newHeap;
            }

            var bubbleIndex = _numberOfNodes;
            _binaryHeap [bubbleIndex] = node;

            var pushComparison = _order == BinaryHeapOrder.SmallFirst ? -1 : 1;
            while (bubbleIndex != 1)
            {
                var parentIndex = bubbleIndex / 2;
                
                if (node.CompareTo(_binaryHeap [parentIndex]) == pushComparison)
                {
                    _binaryHeap [bubbleIndex] = _binaryHeap [parentIndex];
                    _binaryHeap [parentIndex] = node;
                    bubbleIndex = parentIndex;
                }
                else
                {
                    break;
                }
            }

            ++_numberOfNodes;
        }

        /// <summary>
        ///     Attempts to pop.
        /// </summary>
        /// <param name="pop">  [out] The pop. </param>
        /// <returns>
        ///     True if it succeeds, false if it fails.
        /// </returns>
        public bool TryPop(out T pop)
        {
            var popWillWork = _numberOfNodes != 1;
            pop = Pop();
            return popWillWork;
        }

        /// <summary>
        ///     Returns the top-of-stack object without removing it.
        /// </summary>
        /// <returns>
        ///     The current top-of-stack object.
        /// </returns>
        public T Peek()
        {
            return (_numberOfNodes != 1) ?
                        _binaryHeap [1]
                        : default(T);
        }

        /// <summary>
        ///     Removes and returns the top-of-stack object.
        /// </summary>
        /// <returns>
        ///     The previous top-of-stack object. If the BinaryHeap is empty return the default(T).
        /// </returns>
        public T Pop()
        {
            if (_numberOfNodes == 1)
            {
                return default(T);
            }

            _numberOfNodes--;
            var returnItem = _binaryHeap [1];
            Heapify(1);
            return returnItem;
        }

        /// <summary>
        /// Removes the node described by node.
        /// </summary>
        ///
        /// <param name="node"> The node to push. </param>
        public void RemoveNode(T node)
        {
            var nodeIndex = -1;
            for (int i = 1; i < _numberOfNodes; i++)
            {
                if (_binaryHeap[i].CompareTo(node) == 0)
                {
                    nodeIndex = i;
                    break;
                }
            }

            if (nodeIndex == -1)
            {
                return;
            }

            _binaryHeap[nodeIndex] = _binaryHeap[--_numberOfNodes];
            Heapify(nodeIndex);

        }

        /// <summary>
        /// Adds an or update order.
        /// </summary>
        ///
        /// <param name="node"> The node to push or update order. </param>
        public void AddOrUpdate(T node)
        {
            var nodeIndex = -1;
            for (int i = 1; i < _numberOfNodes; i++)
            {
                if (_binaryHeap[i].CompareTo(node) == 0)
                {
                    nodeIndex = i;
                    break;
                }
            }

            if (nodeIndex == -1)
            {
                Push(node);
            }
            else
            {
                //Remove the node then add it again. 
                _binaryHeap[nodeIndex] = _binaryHeap[--_numberOfNodes];
                Heapify(nodeIndex);
                Push(node);
            }
        }

        private void Heapify(int index)
        {
            _binaryHeap [index] = _binaryHeap [_numberOfNodes];

            var swapItem = index;
            int parent;

            do
            {
                parent = swapItem;
                var doubleParent = parent * 2;

                if (doubleParent > _numberOfNodes)
                {
                    continue;
                }
                
                if(AllowSwap(swapItem, doubleParent))
                {
                    swapItem = doubleParent;
                }

                // Both children exist
                if (doubleParent + 1 <= _numberOfNodes)
                {
                    if(AllowSwap(swapItem, doubleParent + 1))
                    {
                        swapItem = doubleParent + 1;
                    }
                }

                // One if the parent's children are smaller or equal, swap them
                if (parent != swapItem)
                {
                    var tmpIndex = _binaryHeap [parent];
                    _binaryHeap [parent] = _binaryHeap [swapItem];
                    _binaryHeap [swapItem] = tmpIndex;
                }
            }
            while (parent != swapItem);
        }
        
        private bool AllowSwap(int current, int parent )
        {
            var comparison = _binaryHeap[current].CompareTo(_binaryHeap[parent]);
            switch (_order)
            {
                case BinaryHeapOrder.SmallFirst:
                    return comparison >= 0;
                    
                case BinaryHeapOrder.BigFirst:
                    return comparison <= 0;
            }

            return false;
        }
    }



    /// <summary>
    /// Values that represent binary heap orders.
    /// </summary>
    public enum BinaryHeapOrder
    {

        /// <summary>
        /// An enum constant representing the small first option.
        /// </summary>
        SmallFirst,

        /// <summary>
        /// An enum constant representing the high first option.
        /// </summary>
        BigFirst
    }
}