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;
}
}
}
}
Fibonacci Heap
B
