FibonacciHeap.cs

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

namespace DataStructures.Heap.FibonacciHeap
{
    /// <summary>
    ///     A generic implementation of a Fibonacci heap.
    /// </summary>
    /// <remarks>
    ///     <para>
    ///         A Fibonacci heap is similar to a standard binary heap
    ///         <see cref="DataStructures.Heap.BinaryHeap{T}" />, however it uses concepts
    ///         of amortized analysis to provide theoretical speedups on common operations like
    ///         insert, union, and decrease-key while maintaining the same speed on all other
    ///         operations.
    ///     </para>
    ///     <para>
    ///         In practice, Fibonacci heaps are more complicated than binary heaps and require
    ///         a large input problems before the benifits of the theoretical speed up
    ///         begin to show.
    ///     </para>
    ///     <para>
    ///         References:
    ///         [1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest,
    ///         and Clifford Stein. 2009. Introduction to Algorithms, Third Edition (3rd. ed.).
    ///         The MIT Press.
    ///     </para>
    /// </remarks>
    /// <typeparam name="T">Type of elements in binary heap.</typeparam>
    public class FibonacciHeap<T> where T : IComparable
    {
        /// <summary>
        ///     Gets or sets the count of the number of nodes in the Fibonacci heap.
        /// </summary>
        public int Count { get; set; }

        /// <summary>
        ///     Gets or sets a reference to the MinItem. The MinItem and all of its siblings
        ///     comprise the root list, a list of trees that satisfy the heap property and
        ///     are joined in a circularly doubly linked list.
        /// </summary>
        private FHeapNode<T>? MinItem { get; set; }

        /// <summary>
        ///     Add item <c>x</c> to this Fibonacci heap.
        /// </summary>
        /// <remarks>
        ///     To add an item to a Fibonacci heap, we simply add it to the "root list",
        ///     a circularly doubly linked list where our minimum item sits. Since adding
        ///     items to a linked list takes O(1) time, the overall time to perform this
        ///     operation is O(1).
        /// </remarks>
        /// <param name="x">An item to push onto the heap.</param>
        /// <returns>
        ///     A reference to the item as it is in the heap. This is used for
        ///     operations like decresing key.
        /// </returns>
        public FHeapNode<T> Push(T x)
        {
            Count++;

            var newItem = new FHeapNode<T>(x);

            if (MinItem == null)
            {
                MinItem = newItem;
            }
            else
            {
                MinItem.AddRight(newItem);

                if (newItem.Key.CompareTo(MinItem.Key) < 0)
                {
                    MinItem = newItem;
                }
            }

            return newItem;
        }

        /// <summary>
        ///     Combines all the elements of two fibonacci heaps.
        /// </summary>
        /// <remarks>
        ///     To union two Fibonacci heaps is a single fibonacci heap is a single heap
        ///     that contains all the elements of both heaps. This can be done in O(1) time
        ///     by concatenating the root lists together.
        ///     For more details on how two circularly linked lists are concatenated, see
        ///     <see cref="FHeapNode{T}.ConcatenateRight" />
        ///     Finally, check to see which of <c>this.MinItem</c> and <c>other.MinItem</c>
        ///     is smaller, and set <c>this.MinItem</c> accordingly
        ///     This operation destroys <c>other</c>.
        /// </remarks>
        /// <param name="other">
        ///     Another heap whose elements we wish to add to this heap.
        ///     The other heap will be destroyed as a result.
        /// </param>
        public void Union(FibonacciHeap<T> other)
        {
            // If there are no items in the other heap, then there is nothing to do.
            if (other.MinItem == null)
            {
                return;
            }

            // If this heap is empty, simply set it equal to the other heap
            if (MinItem == null)
            {
                // Set this heap to the other one
                MinItem = other.MinItem;
                Count = other.Count;

                // Destroy the other heap
                other.MinItem = null;
                other.Count = 0;

                return;
            }

            Count += other.Count;

            // <see cref="DataStructures.FibonacciHeap{T}.FHeapNode.ConcatenateRight(DataStructures.FibonacciHeap{T}.FHeapNode)"/>
            MinItem.ConcatenateRight(other.MinItem);

            // Set the MinItem to the smaller of the two MinItems
            if (other.MinItem.Key.CompareTo(MinItem.Key) < 0)
            {
                MinItem = other.MinItem;
            }

            other.MinItem = null;
            other.Count = 0;
        }

        /// <summary>
        ///     Return the MinItem and remove it from the heap.
        /// </summary>
        /// <remarks>
        ///     This function (with all of its helper functions) is the most complicated
        ///     part of the Fibonacci Heap. However, it can be broken down into a few steps.
        ///     <list type="number">
        ///         <item>
        ///             Add the children of MinItem to the root list. Either one of these children,
        ///             or another of the items in the root list is a candidate to become the new
        ///             MinItem.
        ///         </item>
        ///         <item>
        ///             Remove the MinItem from the root list and appoint a new MinItem temporarily.
        ///         </item>
        ///         <item>
        ///             <see cref="Consolidate" /> what's left
        ///             of the heap.
        ///         </item>
        ///     </list>
        /// </remarks>
        /// <returns>The minimum item from the heap.</returns>
        public T Pop()
        {
            FHeapNode<T>? z = null;
            if (MinItem == null)
            {
                throw new InvalidOperationException("Heap is empty!");
            }

            z = MinItem;

            // Since z is leaving the heap, add its children to the root list
            if (z.Child != null)
            {
                foreach (var x in SiblingIterator(z.Child))
                {
                    x.Parent = null;
                }

                // This effectively adds each child x to the root list
                z.ConcatenateRight(z.Child);
            }

            if (Count == 1)
            {
                MinItem = null;
                Count = 0;
                return z.Key;
            }

            // Temporarily reassign MinItem to an arbitrary item in the root
            // list
            MinItem = MinItem.Right;

            // Remove the old MinItem from the root list altogether
            z.Remove();

            // Consolidate the heap
            Consolidate();

            Count -= 1;

            return z.Key;
        }

        /// <summary>
        ///     A method to see what's on top of the heap without changing its structure.
        /// </summary>
        /// <returns>
        ///     Returns the top element without popping it from the structure of
        ///     the heap.
        /// </returns>
        public T Peek()
        {
            if (MinItem == null)
            {
                throw new InvalidOperationException("The heap is empty");
            }

            return MinItem.Key;
        }

        /// <summary>
        ///     Reduce the key of x to be k.
        /// </summary>
        /// <remarks>
        ///     k must be less than x.Key, increasing the key of an item is not supported.
        /// </remarks>
        /// <param name="x">The item you want to reduce in value.</param>
        /// <param name="k">The new value for the item.</param>
        public void DecreaseKey(FHeapNode<T> x, T k)
        {
            if (MinItem == null)
            {
                throw new ArgumentException($"{nameof(x)} is not from the heap");
            }

            if (x.Key == null)
            {
                throw new ArgumentException("x has no value");
            }

            if (k.CompareTo(x.Key) > 0)
            {
                throw new InvalidOperationException("Value cannot be increased");
            }

            x.Key = k;
            var y = x.Parent;
            if (y != null && x.Key.CompareTo(y.Key) < 0)
            {
                Cut(x, y);
                CascadingCut(y);
            }

            if (x.Key.CompareTo(MinItem.Key) < 0)
            {
                MinItem = x;
            }
        }

        /// <summary>
        ///     Remove x from the child list of y.
        /// </summary>
        /// <param name="x">A child of y we just decreased the value of.</param>
        /// <param name="y">The now former parent of x.</param>
        protected void Cut(FHeapNode<T> x, FHeapNode<T> y)
        {
            if (MinItem == null)
            {
                throw new InvalidOperationException("Heap malformed");
            }

            if (y.Degree == 1)
            {
                y.Child = null;
                MinItem.AddRight(x);
            }
            else if (y.Degree > 1)
            {
                x.Remove();
            }
            else
            {
                throw new InvalidOperationException("Heap malformed");
            }

            y.Degree--;
            x.Mark = false;
            x.Parent = null;
        }

        /// <summary>
        ///     Rebalances the heap after the decrease operation takes place.
        /// </summary>
        /// <param name="y">An item that may no longer obey the heap property.</param>
        protected void CascadingCut(FHeapNode<T> y)
        {
            var z = y.Parent;
            if (z != null)
            {
                if (!y.Mark)
                {
                    y.Mark = true;
                }
                else
                {
                    Cut(y, z);
                    CascadingCut(z);
                }
            }
        }

        /// <summary>
        ///     <para>
        ///         Consolidate is analogous to Heapify in <see cref="DataStructures.Heap.BinaryHeap{T}" />.
        ///     </para>
        ///     <para>
        ///         First, an array <c>A</c> [0...D(H.n)] is created where H.n is the number
        ///         of items in this heap, and D(x) is the max degree any node can have in a
        ///         Fibonacci heap with x nodes.
        ///     </para>
        ///     <para>
        ///         For each node <c>x</c> in the root list, try to add it to <c>A[d]</c> where
        ///         d is the degree of <c>x</c>.
        ///         If there is already a node in <c>A[d]</c>, call it <c>y</c>, and make
        ///         <c>y</c> a child of <c>x</c>. (Swap <c>x</c> and <c>y</c> beforehand if
        ///         <c>x</c> is greater than <c>y</c>). Now that <c>x</c> has one more child,
        ///         remove if from <c>A[d]</c> and add it to <c>A[d+1]</c> to reflect that its
        ///         degree is one more. Loop this behavior until we find an empty spot to put
        ///         <c>x</c>.
        ///     </para>
        ///     <para>
        ///         With <c>A</c> all filled, empty the root list of the heap. And add each item
        ///         from <c>A</c> into the root list, one by one, making sure to keep track of
        ///         which is smallest.
        ///     </para>
        /// </summary>
        protected void Consolidate()
        {
            if (MinItem == null)
            {
                return;
            }

            // There's a fact in Intro to Algorithms:
            // "the max degree of any node in an n-node fibonacci heap is O(lg(n)).
            // In particular, we shall show that D(n) <= floor(log_phi(n)) where phi is
            // the golden ratio, defined in equation 3.24 as phi = (1 + sqrt(5))/2"
            //
            // For a proof, see [1]
            var maxDegree = 1 + (int)Math.Log(Count, (1 + Math.Sqrt(5)) / 2);

            // Create slots for every possible node degree of x
            var a = new FHeapNode<T>?[maxDegree];
            var siblings = SiblingIterator(MinItem).ToList();
            foreach (var w in siblings)
            {
                var x = w;
                var d = x.Degree;

                var y = a[d];

                // While A[d] is not empty, we can't blindly put x here
                while (y != null)
                {
                    if (x.Key.CompareTo(y.Key) > 0)
                    {
                        // Exchange x and y
                        var temp = x;
                        x = y;
                        y = temp;
                    }

                    // Make y a child of x
                    FibHeapLink(y, x);

                    // Empty out this spot since x now has a higher degree
                    a[d] = null;

                    // Add 1 to x's degree before going back into the loop
                    d++;

                    y = a[d];
                }

                // Now that there's an empty spot for x, place it there
                a[d] = x;
            }

            ReconstructHeap(a);
        }

        /// <summary>
        ///     Reconstructs the heap based on the array of node degrees created by the consolidate step.
        /// </summary>
        /// <param name="a">An array of FHeapNodes where a[i] represents a node of degree i.</param>
        private void ReconstructHeap(FHeapNode<T>?[] a)
        {
            // Once all items are in A, empty out the root list
            MinItem = null;

            for (var i = 0; i < a.Length; i++)
            {
                var r = a[i];
                if (r == null)
                {
                    continue;
                }

                if (MinItem == null)
                {
                    // If the root list is completely empty, make this the new
                    // MinItem
                    MinItem = r;

                    // Make a new root list with just this item. Make sure to make
                    // it its own list.
                    MinItem.SetSiblings(MinItem, MinItem);
                    MinItem.Parent = null;
                }
                else
                {
                    // Add A[i] to the root list
                    MinItem.AddRight(r);

                    // If this item is smaller, make it the new min item
                    if (MinItem.Key.CompareTo(r.Key) > 0)
                    {
                        MinItem = a[i];
                    }
                }
            }
        }

        /// <summary>
        ///     Make y a child of x.
        /// </summary>
        /// <param name="y">A node to become the child of x.</param>
        /// <param name="x">A node to become the parent of y.</param>
        private void FibHeapLink(FHeapNode<T> y, FHeapNode<T> x)
        {
            y.Remove();
            x.AddChild(y);
            y.Mark = false;
        }

        /// <summary>
        ///     A helper function to iterate through all the siblings of this node in the
        ///     circularly doubly linked list.
        /// </summary>
        /// <param name="node">A node we want the siblings of.</param>
        /// <returns>An iterator over all of the siblings.</returns>
        private IEnumerable<FHeapNode<T>> SiblingIterator(FHeapNode<T> node)
        {
            var currentNode = node;
            yield return currentNode;

            currentNode = node.Right;
            while (currentNode != node)
            {
                yield return currentNode;
                currentNode = currentNode.Right;
            }
        }
    }
}