MinMaxHeap.cs

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

namespace DataStructures.Heap
{
    /// <summary>
    ///     This class implements min-max heap.
    ///     It provides functionality of both min-heap and max-heap with the same time complexity.
    ///     Therefore it provides constant time retrieval and logarithmic time removal
    ///     of both the minimum and maximum elements in it.
    /// </summary>
    /// <typeparam name="T">Generic type.</typeparam>
    public class MinMaxHeap<T>
    {
        private readonly List<T> heap;

        /// <summary>
        ///     Initializes a new instance of the <see cref="MinMaxHeap{T}" /> class that contains
        ///     elements copied from a specified enumerable collection and that uses a specified comparer.
        /// </summary>
        /// <param name="collection">The enumerable collection to be copied.</param>
        /// <param name="comparer">The default comparer to use for comparing objects.</param>
        public MinMaxHeap(IEnumerable<T>? collection = null, IComparer<T>? comparer = null)
        {
            Comparer = comparer ?? Comparer<T>.Default;
            collection ??= Enumerable.Empty<T>();

            heap = collection.ToList();
            for (var i = Count / 2 - 1; i >= 0; --i)
            {
                PushDown(i);
            }
        }

        /// <summary>
        ///     Gets the  <see cref="IComparer{T}" />. object that is used to order the values in the <see cref="MinMaxHeap{T}" />.
        /// </summary>
        public IComparer<T> Comparer { get; }

        /// <summary>
        ///     Gets the number of elements in the <see cref="MinMaxHeap{T}" />.
        /// </summary>
        public int Count => heap.Count;

        /// <summary>
        ///     Adds an element to the heap.
        /// </summary>
        /// <param name="item">The element to add to the heap.</param>
        public void Add(T item)
        {
            heap.Add(item);
            PushUp(Count - 1);
        }

        /// <summary>
        ///     Removes the maximum node from the heap and returns its value.
        /// </summary>
        /// <exception cref="InvalidOperationException">Thrown if heap is empty.</exception>
        /// <returns>Value of the removed maximum node.</returns>
        public T ExtractMax()
        {
            if (Count == 0)
            {
                throw new InvalidOperationException("Heap is empty");
            }

            var max = GetMax();
            RemoveNode(GetMaxNodeIndex());
            return max;
        }

        /// <summary>
        ///     Removes the minimum node from the heap and returns its value.
        /// </summary>
        /// <exception cref="InvalidOperationException">Thrown if heap is empty.</exception>
        /// <returns>Value of the removed minimum node.</returns>
        public T ExtractMin()
        {
            if (Count == 0)
            {
                throw new InvalidOperationException("Heap is empty");
            }

            var min = GetMin();
            RemoveNode(0);
            return min;
        }

        /// <summary>
        ///     Gets the maximum value in the heap, as defined by the comparer.
        /// </summary>
        /// <exception cref="InvalidOperationException">Thrown if heap is empty.</exception>
        /// <returns>The maximum value in the heap.</returns>
        public T GetMax()
        {
            if (Count == 0)
            {
                throw new InvalidOperationException("Heap is empty");
            }

            return heap[GetMaxNodeIndex()];
        }

        /// <summary>
        ///     Gets the minimum value in the heap, as defined by the comparer.
        /// </summary>
        /// <exception cref="InvalidOperationException">Thrown if heap is empty.</exception>
        /// <returns>The minimum value in the heap.</returns>
        public T GetMin()
        {
            if (Count == 0)
            {
                throw new InvalidOperationException("Heap is empty");
            }

            return heap[0];
        }

        /// <summary>
        ///     Finds maximum value among children and grandchildren of the specified node.
        /// </summary>
        /// <param name="index">Index of the node in the Heap array.</param>
        /// <returns>Index of the maximum descendant.</returns>
        private int IndexOfMaxChildOrGrandchild(int index)
        {
            var descendants = new[]
            {
                2 * index + 1,
                2 * index + 2,
                4 * index + 3,
                4 * index + 4,
                4 * index + 5,
                4 * index + 6,
            };
            var resIndex = descendants[0];
            foreach (var descendant in descendants)
            {
                if (descendant >= Count)
                {
                    break;
                }

                if (Comparer.Compare(heap[descendant], heap[resIndex]) > 0)
                {
                    resIndex = descendant;
                }
            }

            return resIndex;
        }

        /// <summary>
        ///     Finds minumum value among children and grandchildren of the specified node.
        /// </summary>
        /// <param name="index">Index of the node in the Heap array.</param>
        /// <returns>Index of the minimum descendant.</returns>
        private int IndexOfMinChildOrGrandchild(int index)
        {
            var descendants = new[] { 2 * index + 1, 2 * index + 2, 4 * index + 3, 4 * index + 4, 4 * index + 5, 4 * index + 6 };
            var resIndex = descendants[0];
            foreach (var descendant in descendants)
            {
                if (descendant >= Count)
                {
                    break;
                }

                if (Comparer.Compare(heap[descendant], heap[resIndex]) < 0)
                {
                    resIndex = descendant;
                }
            }

            return resIndex;
        }

        private int GetMaxNodeIndex()
        {
            return Count switch
            {
                0 => throw new InvalidOperationException("Heap is empty"),
                1 => 0,
                2 => 1,
                _ => Comparer.Compare(heap[1], heap[2]) > 0 ? 1 : 2,
            };
        }

        private bool HasChild(int index) => index * 2 + 1 < Count;

        private bool IsGrandchild(int node, int grandchild) => grandchild > 2 && Grandparent(grandchild) == node;

        /// <summary>
        ///     Checks if node at index belongs to Min or Max level of the heap.
        ///     Root node belongs to Min level, its children - Max level,
        ///     its grandchildren - Min level, and so on.
        /// </summary>
        /// <param name="index">Index to check.</param>
        /// <returns>true if index is at Min level; false if it is at Max Level.</returns>
        private bool IsMinLevelIndex(int index)
        {
            // For all Min levels, value (index + 1) has the leftmost bit set to '1' at even position.
            const uint minLevelsBits = 0x55555555;
            const uint maxLevelsBits = 0xAAAAAAAA;
            return ((index + 1) & minLevelsBits) > ((index + 1) & maxLevelsBits);
        }

        private int Parent(int index) => (index - 1) / 2;

        private int Grandparent(int index) => ((index - 1) / 2 - 1) / 2;

        /// <summary>
        ///     Assuming that children sub-trees are valid heaps, pushes node to lower levels
        ///     to make heap valid.
        /// </summary>
        /// <param name="index">Node index.</param>
        private void PushDown(int index)
        {
            if (IsMinLevelIndex(index))
            {
                PushDownMin(index);
            }
            else
            {
                PushDownMax(index);
            }
        }

        private void PushDownMax(int index)
        {
            if (!HasChild(index))
            {
                return;
            }

            var maxIndex = IndexOfMaxChildOrGrandchild(index);

            // If smaller element are put at min level (as result of swaping), it doesn't affect sub-tree validity.
            // If smaller element are put at max level, PushDownMax() should be called for that node.
            if (IsGrandchild(index, maxIndex))
            {
                if (Comparer.Compare(heap[maxIndex], heap[index]) > 0)
                {
                    SwapNodes(maxIndex, index);
                    if (Comparer.Compare(heap[maxIndex], heap[Parent(maxIndex)]) < 0)
                    {
                        SwapNodes(maxIndex, Parent(maxIndex));
                    }

                    PushDownMax(maxIndex);
                }
            }
            else
            {
                if (Comparer.Compare(heap[maxIndex], heap[index]) > 0)
                {
                    SwapNodes(maxIndex, index);
                }
            }
        }

        private void PushDownMin(int index)
        {
            if (!HasChild(index))
            {
                return;
            }

            var minIndex = IndexOfMinChildOrGrandchild(index);

            // If bigger element are put at max level (as result of swaping), it doesn't affect sub-tree validity.
            // If bigger element are put at min level, PushDownMin() should be called for that node.
            if (IsGrandchild(index, minIndex))
            {
                if (Comparer.Compare(heap[minIndex], heap[index]) < 0)
                {
                    SwapNodes(minIndex, index);
                    if (Comparer.Compare(heap[minIndex], heap[Parent(minIndex)]) > 0)
                    {
                        SwapNodes(minIndex, Parent(minIndex));
                    }

                    PushDownMin(minIndex);
                }
            }
            else
            {
                if (Comparer.Compare(heap[minIndex], heap[index]) < 0)
                {
                    SwapNodes(minIndex, index);
                }
            }
        }

        /// <summary>
        ///     Having a new node in the heap, swaps this node with its ancestors to make heap valid.
        ///     For node at min level. If new node is less than its parent, then it is surely less then
        ///     all other nodes on max levels on path to the root of the heap. So node are pushed up, by
        ///     swaping with its grandparent, until they are ordered correctly.
        ///     For node at max level algorithm is analogical.
        /// </summary>
        /// <param name="index">Index of the new node.</param>
        private void PushUp(int index)
        {
            if (index == 0)
            {
                return;
            }

            var parent = Parent(index);

            if (IsMinLevelIndex(index))
            {
                if (Comparer.Compare(heap[index], heap[parent]) > 0)
                {
                    SwapNodes(index, parent);
                    PushUpMax(parent);
                }
                else
                {
                    PushUpMin(index);
                }
            }
            else
            {
                if (Comparer.Compare(heap[index], heap[parent]) < 0)
                {
                    SwapNodes(index, parent);
                    PushUpMin(parent);
                }
                else
                {
                    PushUpMax(index);
                }
            }
        }

        private void PushUpMax(int index)
        {
            if (index > 2)
            {
                var grandparent = Grandparent(index);
                if (Comparer.Compare(heap[index], heap[grandparent]) > 0)
                {
                    SwapNodes(index, grandparent);
                    PushUpMax(grandparent);
                }
            }
        }

        private void PushUpMin(int index)
        {
            if (index > 2)
            {
                var grandparent = Grandparent(index);
                if (Comparer.Compare(heap[index], heap[grandparent]) < 0)
                {
                    SwapNodes(index, grandparent);
                    PushUpMin(grandparent);
                }
            }
        }

        private void RemoveNode(int index)
        {
            SwapNodes(index, Count - 1);
            heap.RemoveAt(Count - 1);
            if (Count != 0)
            {
                PushDown(index);
            }
        }

        private void SwapNodes(int i, int j)
        {
            var temp = heap[i];
            heap[i] = heap[j];
            heap[j] = temp;
        }
    }
}