BinaryHeap.cs

using System;
using System.Collections.Generic;

namespace DataStructures.Heap
{
    /// <summary>
    ///     A generic implementation of a binary heap.
    /// </summary>
    /// <remarks>
    ///     A binary heap is a complete binary tree that satisfies the heap property;
    ///     that is every node in the tree compares greater/less than or equal to its left and right
    ///     child nodes. Note that this is different from a binary search tree, where every node
    ///     must be the largest/smallest node of all of its children.
    ///     Although binary heaps are not very efficient, they are (probably) the simpliest heaps
    ///     to understand and implement.
    ///     More information: https://en.wikipedia.org/wiki/Binary_heap .
    /// </remarks>
    /// <typeparam name="T">Type of elements in binary heap.</typeparam>
    public class BinaryHeap<T>
    {
        /// <summary>
        ///     Comparer to use when comparing elements.
        /// </summary>
        private readonly Comparer<T> comparer;

        /// <summary>
        ///     List to hold the elements of the heap.
        /// </summary>
        private readonly List<T> data;

        /// <summary>
        ///     Initializes a new instance of the <see cref="BinaryHeap{T}" /> class.
        /// </summary>
        public BinaryHeap()
        {
            data = new List<T>();
            comparer = Comparer<T>.Default;
        }

        /// <summary>
        ///     Initializes a new instance of the <see cref="BinaryHeap{T}" /> class with a custom comparision function.
        /// </summary>
        /// <param name="customComparer">The custom comparing function to use to compare elements.</param>
        public BinaryHeap(Comparer<T> customComparer)
        {
            data = new List<T>();
            comparer = customComparer;
        }

        /// <summary>
        ///     Gets the number of elements in the heap.
        /// </summary>
        public int Count => data.Count;

        /// <summary>
        ///     Add an element to the binary heap.
        /// </summary>
        /// <remarks>
        ///     Adding to the heap is done by append the element to the end of the backing list,
        ///     and pushing the added element up until the heap property is restored.
        /// </remarks>
        /// <param name="element">The element to add to the heap.</param>
        /// <exception cref="ArgumentException">Thrown if element is already in heap.</exception>
        public void Push(T element)
        {
            data.Add(element);
            HeapifyUp(data.Count - 1);
        }

        /// <summary>
        ///     Remove the top/root of the binary heap (ie: the largest/smallest element).
        /// </summary>
        /// <remarks>
        ///     Removing from the heap is done by swapping the top/root with the last element in
        ///     the backing list, removing the last element, and pushing the new root down
        ///     until the heap property is restored.
        /// </remarks>
        /// <returns>The top/root of the heap.</returns>
        /// <exception cref="InvalidOperationException">Thrown if heap is empty.</exception>
        public T Pop()
        {
            if (Count == 0)
            {
                throw new InvalidOperationException("Heap is empty!");
            }

            var elem = data[0];
            data[0] = data[^1];
            data.RemoveAt(data.Count - 1);
            HeapifyDown(0);

            return elem;
        }

        /// <summary>
        ///     Return the top/root of the heap without removing it.
        /// </summary>
        /// <returns>The top/root of the heap.</returns>
        /// <exception cref="InvalidOperationException">Thrown if heap is empty.</exception>
        public T Peek()
        {
            if (Count == 0)
            {
                throw new InvalidOperationException("Heap is empty!");
            }

            return data[0];
        }

        /// <summary>
        ///     Returns element if it compares larger to the top/root of the heap, else
        ///     inserts element into the heap and returns the top/root of the heap.
        /// </summary>
        /// <param name="element">The element to check/insert.</param>
        /// <returns>element if element compares larger than top/root of heap, top/root of heap otherwise.</returns>
        public T PushPop(T element)
        {
            if (Count == 0)
            {
                return element;
            }

            if (comparer.Compare(element, data[0]) < 0)
            {
                var tmp = data[0];
                data[0] = element;
                HeapifyDown(0);
                return tmp;
            }

            return element;
        }

        /// <summary>
        ///     Check if element is in the heap.
        /// </summary>
        /// <param name="element">The element to check for.</param>
        /// <returns>true if element is in the heap, false otherwise.</returns>
        public bool Contains(T element) => data.Contains(element);

        /// <summary>
        ///     Remove an element from the heap.
        /// </summary>
        /// <remarks>
        ///     In removing an element from anywhere in the heap, we only need to push down or up
        ///     the replacement value depending on how the removed value compares to its
        ///     replacement value.
        /// </remarks>
        /// <param name="element">The element to remove from the heap.</param>
        /// <exception cref="ArgumentException">Thrown if element is not in heap.</exception>
        public void Remove(T element)
        {
            var idx = data.IndexOf(element);

            if (idx == -1)
            {
                throw new ArgumentException($"{element} not in heap!");
            }

            Swap(idx, data.Count - 1);
            var tmp = data[^1];
            data.RemoveAt(data.Count - 1);

            if (idx < data.Count)
            {
                if (comparer.Compare(tmp, data[idx]) > 0)
                {
                    HeapifyDown(idx);
                }
                else
                {
                    HeapifyUp(idx);
                }
            }
        }

        /// <summary>
        ///     Swap the elements in the heap array at the given indices.
        /// </summary>
        /// <param name="idx1">First index.</param>
        /// <param name="idx2">Second index.</param>
        private void Swap(int idx1, int idx2)
        {
            var tmp = data[idx1];
            data[idx1] = data[idx2];
            data[idx2] = tmp;
        }

        /// <summary>
        ///     Recursive function to restore heap properties.
        /// </summary>
        /// <remarks>
        ///     Restores heap property by swapping the element at <paramref name="elemIdx" />
        ///     with its parent if the element compares greater than its parent.
        /// </remarks>
        /// <param name="elemIdx">The element to check with its parent.</param>
        private void HeapifyUp(int elemIdx)
        {
            var parent = (elemIdx - 1) / 2;

            if (parent >= 0 && comparer.Compare(data[elemIdx], data[parent]) > 0)
            {
                Swap(elemIdx, parent);
                HeapifyUp(parent);
            }
        }

        /// <summary>
        ///     Recursive function to restore heap properties.
        /// </summary>
        /// <remarks>
        ///     Restores heap property by swapping the element at <paramref name="elemIdx" />
        ///     with the larger of its children.
        /// </remarks>
        /// <param name="elemIdx">The element to check with its children.</param>
        private void HeapifyDown(int elemIdx)
        {
            var left = 2 * elemIdx + 1;
            var right = 2 * elemIdx + 2;

            var leftLargerThanElem = left < Count && comparer.Compare(data[elemIdx], data[left]) < 0;
            var rightLargerThanElem = right < Count && comparer.Compare(data[elemIdx], data[right]) < 0;
            var leftLargerThanRight = left < Count && right < Count && comparer.Compare(data[left], data[right]) > 0;

            if (leftLargerThanElem && leftLargerThanRight)
            {
                Swap(elemIdx, left);
                HeapifyDown(left);
            }
            else if (rightLargerThanElem && !leftLargerThanRight)
            {
                Swap(elemIdx, right);
                HeapifyDown(right);
            }
        }
    }
}