< Summary

Information
Class: MoreStructures.PriorityQueues.FibonacciHeap.FibonacciHeapPriorityQueue<T>
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/PriorityQueues/FibonacciHeap/FibonacciHeapPriorityQueue.cs
Line coverage
100%
Covered lines: 21
Uncovered lines: 0
Coverable lines: 21
Total lines: 166
Line coverage: 100%
Branch coverage
100%
Covered branches: 2
Total branches: 2
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor()100%1100%
.ctor(...)100%1100%
GetEnumerator()100%2100%
Push(...)100%1100%
PromoteChildToRoot(...)100%1100%

File(s)

/home/runner/work/MoreStructures/MoreStructures/MoreStructures/PriorityQueues/FibonacciHeap/FibonacciHeapPriorityQueue.cs

#LineLine coverage
 1using MoreStructures.PriorityQueues.BinomialHeap;
 2
 3namespace MoreStructures.PriorityQueues.FibonacciHeap;
 4
 5/// <summary>
 6/// An <see cref="IPriorityQueue{T}"/> implementation based on a Fibonacci Max Heap of its items.
 7/// </summary>
 8/// <remarks>
 9///     <para id="definition">
 10///     DEFINITION
 11///     <br/>
 12///     - A <b>Fibonacci Heap</b> is a <b>Binomial Heap</b> which has its <b>heap max property</b> and <b>binomial
 13///       layout</b> invariants always satisfied, but can have <b>unicity of degree</b> temporarily invalidated
 14///       (until next <see cref="BinomialHeapPriorityQueue{T}.Pop"/> operation).
 15///       <br/>
 16///     - Nodes of the heaps can be flagged as <b>losers</b>, meaning that they have lost at least once a children,
 17///       after its promotion to being a new root.
 18///     </para>
 19///     <para id="advantages">
 20///     ADVANTAGES AND DISADVANTAGES
 21///     <br/>
 22///     - This heap implementation is a Binomial Heap refinement which prioritises performance of <see cref="Push"/>
 23///       and update operations over <see cref="BinomialHeapPriorityQueue{T}.Pop"/>.
 24///       <br/>
 25///     - It does so by taking advantage of both the linked list layout and the tree layout, pretty much like
 26///       Binomial Heaps.
 27///       <br/>
 28///     - Implementations based on linked or array lists are really fast at insertion, because they don't internally
 29///       keep the data sorted. However, extraction becomes expensive, for the very same reason that data is unsorted.
 30///       <br/>
 31///     - At the other end of the spectrum, trees are logarithmic at insertion, because they have to keep data at least
 32///       partially sorted, at all time. Extraction, however, is very cheap.
 33///       <br/>
 34///     - So the underlying idea behind Fibonacci Heaps is to combine linked lists and trees, and represent the data as
 35///       a forest of n-ry heap trees, exactly like Binomial Heaps, and exploit the easy insertion in linked list
 36///       (which is not implemented by the standard Push into a Binomial Heap).
 37///       <br/>
 38///     - In doing so, both <see cref="Push(T, int)"/> and update becomes extremely fast, running in O(1) and O(1)
 39///       amortized, respectively.
 40///       <br/>
 41///     - However, unlike <see cref="ArrayList.ArrayListPriorityQueue{T}"/>,
 42///       <see cref="BinomialHeapPriorityQueue{T}.Pop"/> doesn't become a O(n) operation. Instead, it retains
 43///       logarithmic runtime.
 44///       <br/>
 45///     - This proves to be the best compromise for applications such as the Dijkstra algorithm (implemented in
 46///       <see cref="Graphs.ShortestDistance.DijkstraShortestDistanceFinder"/>), which uses a priority queue to find
 47///       the next best vertex.
 48///       <br/>
 49///     - Dijkstra algorithm performs O(e) <see cref="Extensions.UpdatablePriorityQueueExtensions.PushOrUpdate{T}"/>
 50///       operations and O(v) <see cref="BinomialHeapPriorityQueue{T}.Pop"/> operations, where e and v are the number
 51///       of edges and vertices in the graph, respectively.
 52///       <br/>
 53///     - In dense graphs e is O(v^2), so the number of push/update operations is way higher than the number of pop
 54///       operations, and it makes sense to optimize the former, at the cost of the latter.
 55///     </para>
 56/// </remarks>
 57public partial class FibonacciHeapPriorityQueue<T> : BinomialHeapPriorityQueue<T>
 58    where T : notnull
 59{
 60    /// <summary>
 61    /// Builds an empty priority queue.
 62    /// </summary>
 63    public FibonacciHeapPriorityQueue()
 540864        :base()
 540865    {
 540866    }
 67
 68    /// <summary>
 69    /// Builds a deep, separate copy of the provided <paramref name="source"/> priority queue.
 70    /// </summary>
 71    /// <param name="source">The priority queue to be copied over.</param>
 72    /// <remarks>
 73    /// Doesn't copy the items themselves, it only deep-copies the internal structure of the <paramref name="source"/>
 74    /// queue.
 75    /// </remarks>
 76    protected FibonacciHeapPriorityQueue(FibonacciHeapPriorityQueue<T> source)
 23777        :base(source)
 23778    {
 23779    }
 80
 81    #region Public API
 82
 83    /// <inheritdoc path="//*[not(self::remarks)]"/>
 84    /// <remarks>
 85    /// In order to return items in heap order (i.e. the max at each step), it first copies this priority queue into a
 86    /// second temporary queue, which can be mutated without affecting the state of this queue.
 87    /// <br/>
 88    /// It then iterates over the copy, calling <see cref="BinomialHeapPriorityQueue{T}.Pop"/> until it becomes empty.
 89    /// <br/>
 90    /// Time Complexity is O(n * log(n)) (when fully enumerated), because a single
 91    /// <see cref="BinomialHeapPriorityQueue{T}.Pop"/> on a Fibonacci Heap takes logarithmic time, and there are n
 92    /// items to be extracted.
 93    /// <br/>
 94    /// Space Complexity is O(n), as a copy of this queue is required as auxiliary data structure to emit elements in
 95    /// the right order of priority.
 96    /// </remarks>
 97    public override IEnumerator<T> GetEnumerator()
 23798    {
 23799        var copy = new FibonacciHeapPriorityQueue<T>(this);
 5962100        while (copy.Count > 0)
 5733101            yield return copy.Pop().Item;
 229102    }
 103
 104    /// <inheritdoc path="//*[not(self::remarks)]"/>
 105    /// <remarks>
 106    ///     <para id="algorithm">
 107    ///     ALGORITHM
 108    ///     <br/>
 109    ///     - Adds a new singleton tree T (degree 0) to the forest, wrapping the provided <paramref name="item"/> with
 110    ///       its <paramref name="priority"/> into an object R with no children, and wrapping R into a
 111    ///       <see cref="LinkedListNode{T}"/> LLN, which represents the root of T.
 112    ///       <br/>
 113    ///     - If LLN has higher priority than the root with max priority, updates the reference to the root with max
 114    ///       priority, to point to LLN.
 115    ///       <br/>
 116    ///     - Unlike <see cref="BinomialHeapPriorityQueue{T}.Push(T, int)"/>, it doesn't perform any rebalancing of
 117    ///       the forest just yet, meaning that the binomial property may be temporarily violated until the next
 118    ///       <see cref="BinomialHeapPriorityQueue{T}.Pop"/> operation.
 119    ///       <br/>
 120    ///     - The delay of "housekeeping" operations to restore the shape property of a binomial heap, and the grouping
 121    ///       of such "housekeeping" operations into a single batch, executed at the next
 122    ///       <see cref="BinomialHeapPriorityQueue{T}.Pop"/>, is one of the core efficiency mechanisms of the
 123    ///       Fibonacci Heap.
 124    ///     </para>
 125    ///     <para id="complexity">
 126    ///     COMPLEXITY
 127    ///     <br/>
 128    ///     - Adding a new root to the forest of trees is a constant-time operation, since the root is added at
 129    ///       the end of the linked list representing the forest, which keeps references to both ends of the chain of
 130    ///       nodes.
 131    ///       <br/>
 132    ///     - Therefore, Time Complexity and Space Complexity are O(1).
 133    ///       <br/>
 134    ///     - Notice that this operation executes in constant time at the cost of adding a new shallow tree to the
 135    ///       forest. After n <see cref="Push(T, int)"/> consecutive operations, the forest would be made of n trees
 136    ///       of degree 0, which is the shape of a simple heap based on a linked list.
 137    ///       <br/>
 138    ///     - This cost has to be beared by <see cref="BinomialHeapPriorityQueue{T}.Pop"/>, which runs in logarithmic
 139    ///       time but merges trees of the same degree and does so in batch.
 140    ///     </para>
 141    /// </remarks>
 142    public override void Push(T item, int priority)
 14135143    {
 14135144        var prioritizedItem = new PrioritizedItem<T>(item, priority, CurrentPushTimestamp++, PushTimestampEras[^1]);
 14135145        var newRoot = new TreeNode<T> { PrioritizedItem = prioritizedItem };
 14135146        AddRoot(newRoot);
 14135147        RaiseItemPushed(newRoot);
 14135148    }
 149
 150    #endregion
 151
 152    #region Helpers
 153
 154    /// <summary>
 155    /// Promotes the provided <see cref="TreeNode{T}"/>, to being a root, detaching it from its current parent.
 156    /// Also, resets the "loser" flag of the child (behavior specific to Fibonacci Heaps).
 157    /// </summary>
 158    /// <param name="child">A child of a node of a tree in the forest.</param>
 159    protected override void PromoteChildToRoot(TreeNode<T> child)
 38323160    {
 38323161        base.PromoteChildToRoot(child);
 38323162        child.IsALoser = false;
 38323163    }
 164
 165    #endregion
 166}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

.ctor()
.ctor(MoreStructures.PriorityQueues.FibonacciHeap.FibonacciHeapPriorityQueue`1<T>)
GetEnumerator()
Push(T,System.Int32)
PromoteChildToRoot(MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<T>)