< Summary

Information
Class: MoreStructures.PriorityQueues.BinaryHeap.BinaryHeapPriorityQueue<T>
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/PriorityQueues/BinaryHeap/BinaryHeapPriorityQueue.cs
Line coverage
100%
Covered lines: 46
Uncovered lines: 0
Coverable lines: 46
Total lines: 403
Line coverage: 100%
Branch coverage
100%
Covered branches: 6
Total branches: 6
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
get_CurrentPushTimestamp()100%1100%
get_Items()100%1100%
.ctor()100%1100%
.ctor(...)100%1100%
get_Count()100%1100%
GetEnumerator()100%2100%
System.Collections.IEnumerable.GetEnumerator()100%1100%
Peek()100%1100%
Pop()100%1100%
Push(...)100%1100%
PeekKth(...)100%2100%
MergeFrom(...)100%2100%
Clear()100%1100%
RaiseItemPushed(...)100%1100%
RaiseItemPopping(...)100%1100%
RaiseItemsSwapped(...)100%1100%

File(s)

/home/runner/work/MoreStructures/MoreStructures/MoreStructures/PriorityQueues/BinaryHeap/BinaryHeapPriorityQueue.cs

#LineLine coverage
 1using System.Collections;
 2using System.Diagnostics.CodeAnalysis;
 3using MoreStructures.PriorityQueues.ArrayList;
 4
 5namespace MoreStructures.PriorityQueues.BinaryHeap;
 6
 7/// <summary>
 8/// An <see cref="IPriorityQueue{T}"/> implementation based on a Binary Max Heap of its items. On top of basic
 9/// operations it also supports <see cref="IPeekKthPriorityQueue{T}"/> and
 10/// <see cref="IMergeablePriorityQueue{T, TPQTarget}"/>.
 11/// </summary>
 12/// <typeparam name="T"><inheritdoc cref="IPriorityQueue{T}"/></typeparam>
 13/// <remarks>
 14///     <para id="advantages">
 15///     ADVANTAGES AND DISADVANTAGES
 16///     <br/>
 17///     - The Binary Max Heap is used to store items with their priorities, in a way that the item with max priority is
 18///       immediately retrievable (making <see cref="Peek"/> a constant-time operation), and easily extractable (making
 19///       <see cref="Pop"/> a logarithmic-time operation).
 20///       <br/>
 21///     - This comes a cost of the <see cref="Push(T, int)"/> operation, which is O(1) in
 22///       <see cref="ArrayListPriorityQueue{T}"/> and becomes a logarithmic-time operation in this implementation.
 23///       <br/>
 24///     - So this implementation can be considered as a balanced compromise between insertion and extraction, which
 25///       complexifies the underlying data structure and loses some performance in insertion to obtain all-around
 26///       logarithmic performance.
 27///       <br/>
 28///     - Given the "exponentially better" runtime of logarithmic operations w.r.t. linear ones, such compromise makes
 29///       sense for most scenarios.
 30///       <br/>
 31///     - Merging two Binary Max Heap structures, however, still requires linear time. If merging performance is
 32///       critical, a more advanced tree-based implementation, such as
 33///       <see cref="BinomialHeap.BinomialHeapPriorityQueue{T}"/>,
 34///       <see cref="FibonacciHeap.FibonacciHeapPriorityQueue{T}"/> and their derivations, should be used instead.
 35///     </para>
 36///     <para id="heap-representation">
 37///     BINARY MAX HEAP REPRESENTATION
 38///     <br/>
 39///     - The Binary Max Heap used for items and priorities is backed by a complete Binary Tree, represented as an
 40///       Array List of its items.
 41///       <br/>
 42///     - The root of the tree is always in position 0, its children in positions 1 and 2, grand-children in positions
 43///       3, 4, 5 and 6 (where 3 and 4 are children of 1 and 5 and 6 are children of 2), etc.
 44///       <br/>
 45///     - This is the most space-efficient layout for a complete tree, which allows O(1) root access, parent-to-child
 46///       navigation and child-to-parent navigation, by performing simple indexing arithmetic.
 47///       <br/>
 48///     - The underlying Binary Tree is complete, hence balanced: it's height h is Math.Floor(log(n, 2)), where n is
 49///       the number of nodes in the tree. For example a complete Binary Tree of 3 nodes has necessarily height 1,
 50///       whereas one of 4 nodes has to have height 2.
 51///       <br/>
 52///     - While the Binary Tree is complete, it is non necessarily full, meaning that the last level may not be
 53///       entirely filled with leaves and the number of leaves at the last level may vary from 1 up to 2^(h + 1) - 1.
 54///       <br/>
 55///     - All modification operations (such as <see cref="Pop"/>) done on the Binary Max Heap ensure that the tree is
 56///       kept complete and balanced.
 57///     </para>
 58///     <para id="repetitions">
 59///     REPEATED ITEMS AND PRIORITIES
 60///     <br/>
 61///     - Repeated items, as well as repeated priorities, are supported.
 62///       <br/>
 63///     - The implementation is <b>stable</b> both for priorities and items.
 64///       <br/>
 65///     - If two items I1 and I2 are pushed with the same priority P at times T1 and T2 with T1 &lt; T2, when P becomes
 66///       the highest priority in the heap, I1 is popped out of the heap before I2 is.
 67///       <br/>
 68///     - That also applies to the case where I1 and I2 are equal by value and different by reference.
 69///       <br/>
 70///     - Stability is achieved by keeping a "push index", i.e. a <see cref="int"/> counter set to 0 in the constructor
 71///       and incremented every time a new item is introduced in the queue via a <see cref="Push(T, int)"/>.
 72///       <br/>
 73///     - The push index is included in the heap item record, together with the item of type
 74///       <typeparamref name="T"/> and its priority of type <see cref="int"/>.
 75///       <br/>
 76///     - This way two heap item records I1 and I2 with the same priority I1.Priority and I2.Priority, and potentially
 77///       the same or equal items I1.Item and I2.Item, will necessarily differ by push index, I1.PushTimestamp and
 78///       I2.PushTimestamp.
 79///       <br/>
 80///      - Therefore a <b>total strict order</b> can be imposed.
 81///     </para>
 82/// </remarks>
 83public class BinaryHeapPriorityQueue<T>
 84    : IPeekKthPriorityQueue<T>, IMergeablePriorityQueue<T, BinaryHeapPriorityQueue<T>>
 85    where T : notnull
 86{
 87    /// <summary>
 88    /// A non-negative, zero-based, monotonically strictly increasing counter, incremented at every insertion into this
 89    /// data structure by a <see cref="Push(T, int)"/>.
 90    /// </summary>
 4040191    protected int CurrentPushTimestamp { get; set; } = 0;
 92
 93    /// <summary>
 94    /// The wrapped <see cref="IList{T}"/> of <see cref="PrioritizedItem{T}"/> backing the binary max heap.
 95    /// </summary>
 6763196    protected BinaryHeapListWrapper<PrioritizedItem<T>> Items { get; }
 97
 98    /// <summary>
 99    /// Builds an empty priority queue.
 100    /// </summary>
 101    /// <remarks>
 102    /// The underlying data structure for priorities and items is initialized to an empty structure.
 103    /// <br/>
 104    /// Therefore, Time and Space Complexity is O(1).
 105    /// </remarks>
 5577106    public BinaryHeapPriorityQueue()
 5577107    {
 5577108        Items =
 5577109            new(new List<PrioritizedItem<T>>(), Comparer<PrioritizedItem<T>>.Default, 0)
 5577110            {
 5577111                RaiseItemPushed = RaiseItemPushed,
 5577112                RaiseItemPopping = RaiseItemPopping,
 5577113                RaiseItemsSwapped = RaiseItemsSwapped,
 5577114            };
 5577115    }
 116
 117    /// <summary>
 118    /// Builds a new priority queue with the same items of the provided <paramref name="source"/>.
 119    /// </summary>
 120    /// <param name="source">The <see cref="BinaryHeapPriorityQueue{T}"/> instance to use as a source of data.</param>
 121    /// <remarks>
 122    /// The underlying data structure is shallow copied.
 123    /// <br/>
 124    /// Because it is made of immutable records, a shallow-copy is enough to ensure that its mutation in
 125    /// <paramref name="source"/> won't affect the new priority queue or viceversa.
 126    /// <br/>
 127    /// Because the data structure contain O(n) items, Time and Space Complexity are O(n), where n is the number of
 128    /// items in <paramref name="source"/>.
 129    /// </remarks>
 252130    protected BinaryHeapPriorityQueue(BinaryHeapPriorityQueue<T> source)
 252131    {
 252132        Items =
 252133            new(source.Items)
 252134            {
 252135                RaiseItemPushed = RaiseItemPushed,
 252136                RaiseItemPopping = RaiseItemPopping,
 252137                RaiseItemsSwapped = RaiseItemsSwapped,
 252138            };
 252139    }
 140
 141    #region Public API
 142
 143    /// <inheritdoc path="//*[not(self::remarks)]"/>
 144    /// <remarks>
 145    /// Checks the count of the underlying heap.
 146    /// <br/>
 147    /// The size of the heap may be smaller than the size of the underlying list, if there is buffer at the end.
 148    /// <br/>
 149    /// Time and Space Complexity are O(1).
 150    /// </remarks>
 6856151    public virtual int Count => Items.HeapCount;
 152
 153    /// <inheritdoc path="//*[not(self::remarks)]"/>
 154    /// <remarks>
 155    /// In order to return items in heap order (i.e. the max at each step), it first copies this priority queue into a
 156    /// second temporary queue, which can be mutated without affecting the state of this queue.
 157    /// <br/>
 158    /// It then iterates over the copy, calling <see cref="Pop"/> until it becomes empty.
 159    /// <br/>
 160    /// Time Complexity is O(n * log(n)) (when fully enumerated), because a single <see cref="Pop"/> on an complete
 161    /// binary heap takes logarithmic time, and there are n items to be extracted.
 162    /// <br/>
 163    /// Space Complexity is O(n), as a copy of this queue is required as auxiliary data structure to emit elements in
 164    /// the right order of priority.
 165    /// </remarks>
 166    public virtual IEnumerator<T> GetEnumerator()
 252167    {
 252168        var copy = new BinaryHeapPriorityQueue<T>(this);
 5998169        while (copy.Count > 0)
 5754170            yield return copy.Pop().Item;
 244171    }
 172
 173    /// <inheritdoc path="//*[not(self::remarks)]"/>
 174    /// <remarks>
 175    ///     <inheritdoc cref="GetEnumerator"/>
 176    /// </remarks>
 2177    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 178
 179    /// <inheritdoc path="//*[not(self::remarks)]"/>
 180    /// <remarks>
 181    /// Peeks the item with max priority from the root of the heap, if any.
 182    /// <br/>
 183    /// That is located at index 0 in the underlying list, and can be accessed in constant-time.
 184    /// <br/>
 185    /// Therefore, Time and Space Complexity are O(1).
 186    /// </remarks>
 433187    public virtual PrioritizedItem<T> Peek() => Items.Peek();
 188
 189    /// <inheritdoc path="//*[not(self::remarks)]"/>
 190    /// <remarks>
 191    ///     <para id="algorithm">
 192    ///     ALGORITHM
 193    ///     <br/>
 194    ///     - Peeks the first item from the heap and stores to return it as result.
 195    ///       <br/>
 196    ///     - Takes the last item of the heap and moves to the root, in first position.
 197    ///       <br/>
 198    ///     - Restores heap constraints by recursively sifting down new root, as many time as needed.
 199    ///     </para>
 200    ///     <para id="complexity">
 201    ///     COMPLEXITY
 202    ///     <br/>
 203    ///     - <see cref="Peek"/> and removal of item with max priority and last leaf of the heap are all constant-time
 204    ///       operations.
 205    ///       <br/>
 206    ///     - Since the heap is an complete binary tree, the heigh of the three is O(log(n)).
 207    ///       <br/>
 208    ///     - So the number of "sift down" operations is logarithmic w.r.t. the input.
 209    ///       <br/>
 210    ///     - Therefore, Time Complexity is O(log(n)) and Space Complexity is O(1), since modifications are all done
 211    ///       in-place in underlying data structures.
 212    ///     </para>
 213    /// </remarks>
 8425214    public virtual PrioritizedItem<T> Pop() => Items.Pop();
 215
 216    /// <inheritdoc path="//*[not(self::remarks)]"/>
 217    /// <remarks>
 218    ///     Negative priorities are supported.
 219    ///     <para id="algorithm">
 220    ///     ALGORITHM
 221    ///     <br/>
 222    ///     - Adds a new leaf to the heap, carrying priority, item and unique push index.
 223    ///       <br/>
 224    ///     - Restores heap constraints by recursively sifting up new leaf, as many time as needed.
 225    ///     </para>
 226    ///     <para id="complexity">
 227    ///     COMPLEXITY
 228    ///     <br/>
 229    ///     - Adding a new item with given priority and a leaf to the heap are constant-time operations.
 230    ///       <br/>
 231    ///     - Since the heap is an complete binary tree, the heigh of the three is O(log(n)).
 232    ///       <br/>
 233    ///     - So the number of "sift up" operations is logarithmic w.r.t. the input.
 234    ///       <br/>
 235    ///     - Therefore, Time Complexity is O(log(n)) and Space Complexity is O(1), since modifications are all done
 236    ///       in-place in underlying data structure.
 237    ///     </para>
 238    /// </remarks>
 13341239    public virtual void Push(T item, int priority) => Items.Push(new(item, priority, CurrentPushTimestamp++));
 240
 241    /// <inheritdoc path="//*[not(self::remarks)]"/>
 242    /// <remarks>
 243    ///     <para id="algorithm">
 244    ///     ALGORITHM
 245    ///     <br/>
 246    ///     - If <paramref name="k"/> is negative, an <see cref="ArgumentException"/> is returned.
 247    ///       <br/>
 248    ///     - If <paramref name="k"/> is non-smaller than the <see cref="Count"/>, <see langword="null"/> is returned.
 249    ///       <br/>
 250    ///     - If <paramref name="k"/> is 0, <see cref="Peek"/> is returned.
 251    ///       <br/>
 252    ///     - Otherwise, the main algorithm loop is performed, at most <paramref name="k"/> times.
 253    ///       <br/>
 254    ///     - A dedicated <see cref="BinaryHeapPriorityQueue{T}"/> C of <see cref="int"/> values is instantiated.
 255    ///       <br/>
 256    ///     - The values of C are the indexes of the underlying list of this priority queue, and identify candidates
 257    ///       for the <paramref name="k"/>-th largest item.
 258    ///       <br/>
 259    ///     - Such candidates are sorted in C by priority and push timestamps, exactly in the same way they are
 260    ///       sorted in this priority queue.
 261    ///       <br/>
 262    ///     - At the beginning only the root of the priority queue (i.e. index 0) is pushed to C.
 263    ///       <br/>
 264    ///     - At each iteration the max of C is popped from C and its left and right children (if any) are pushed into
 265    ///       C.
 266    ///       <br/>
 267    ///     - After <paramref name="k"/> iterations, the <see cref="Peek"/> of C gives the <paramref name="k"/>-th
 268    ///       largest item.
 269    ///       <br/>
 270    ///     - Notice that C cannot run short of candidates (due to lack of children), because of the preconditions
 271    ///       on <paramref name="k"/>.
 272    ///     </para>
 273    ///     <para id="complexity">
 274    ///     COMPLEXITY
 275    ///     <br/>
 276    ///     - Checks on the value of <paramref name="k"/> w.r.t. the size of this priority queue and direct access to
 277    ///       the underlying list, to return the final result once the index has been found, are both done in constant
 278    ///       time.
 279    ///       <br/>
 280    ///     - Candidates queue instantiation and 1st push into it are also constant time operations.
 281    ///       <br/>
 282    ///     - The main loop consist of k iterations.
 283    ///       <br/>
 284    ///     - At each iteration 1 item is popped and 2 are pushed, so the candidates queue grows of 1 item per cycle.
 285    ///       <br/>
 286    ///     - Each <see cref="Pop"/> and <see cref="Push(T, int)"/> operation on the candidates queue has logarithmic
 287    ///       run, since they are done on a <see cref="BinaryHeapPriorityQueue{T}"/> instance.
 288    ///       <br/>
 289    ///     - Therefore, Time Complexity is O(k * log(k)) and Space Complexity is O(k).
 290    ///     </para>
 291    /// </remarks>
 26292    public virtual PrioritizedItem<T>? PeekKth(int k) => Items.PeekKth(k) is (var result, true) ? result : null;
 293
 294    /// <inheritdoc path="//*[not(self::remarks)]"/>
 295    /// <remarks>
 296    ///     <para id="algorithm">
 297    ///     ALGORITHM
 298    ///     <br/>
 299    ///     - Pushing all items in the <paramref name="targetPriorityQueue"/> via <see cref="Push(T, int)"/>, would
 300    ///       result in O(m * log(m)) Time Complexity, where m is the number of items in the
 301    ///       <paramref name="targetPriorityQueue"/>.
 302    ///       <br/>
 303    ///     - Instead, each of the m items from the <paramref name="targetPriorityQueue"/> is added to the underlying
 304    ///       array list of this queue, at the end.
 305    ///       <br/>
 306    ///     - Then, the content of <paramref name="targetPriorityQueue"/> is cleared, to respect the contract defined
 307    ///       by <see cref="IMergeablePriorityQueue{T, TPQTarget}"/>.
 308    ///       <br/>
 309    ///     - Finally, the heap property is restored globally for all items in the underlying array list, by sifting
 310    ///       down all items in the first half of the list, proceeding backwards from the middle of the list to its
 311    ///       first item.
 312    ///       <br/>
 313    ///     - Such global sift down is required for the first half of the items only, because the second half only
 314    ///       contains leaves of the tree, for which a sift down would do nothing (i.e. the heap property is already
 315    ///       satisfied).
 316    ///     </para>
 317    ///     <para id="complexity">
 318    ///     COMPLEXITY
 319    ///     <br/>
 320    ///     - Appending m items has a linear cost over m.
 321    ///       <br/>
 322    ///     - Clearing the target only takes constant time.
 323    ///       <br/>
 324    ///     - Restoring the heap property globally would seem to take n / 2 * log(n), where n is the total number of
 325    ///       items in this queue, after the merge: the number of items to sift down plus the cost of sifting down the
 326    ///       tree. That would give O(n * log(n)) complexity: not a real improvement over the naive approach of pushing
 327    ///       n items.
 328    ///       <br/>
 329    ///     - However, the length of the path to sift down is not as big as the entire height of the tree. Instead, the
 330    ///       closer the starting node is to the leave, the smaller it becomes: leaves have sift down paths of length
 331    ///       0, their parent of length 1, etc., up to the root, which has sift down path of length equal to the height
 332    ///       of the tree.
 333    ///       <br/>
 334    ///     - A key observation is that in a complete and full tree there are more leaves than all nodes in other
 335    ///       levels combined, and that applies to all levels w.r.t. all smaller levels.
 336    ///       <br/>
 337    ///     - So, sift down will cost less for way more nodes, resulting in overall O(n) Time Complexity.
 338    ///       <br/>
 339    ///     - Space Complexity is O(m), since m items are added to the list storing the items of this queue.
 340    ///     </para>
 341    /// </remarks>
 342    public virtual void MergeFrom(BinaryHeapPriorityQueue<T> targetPriorityQueue)
 236343    {
 5968344        foreach (var prioritizedItem in targetPriorityQueue.Items)
 2630345        {
 2630346            Items.Push(new(prioritizedItem.Item, prioritizedItem.Priority, CurrentPushTimestamp), false);
 2630347            CurrentPushTimestamp++;
 2630348        }
 349
 236350        targetPriorityQueue.Clear();
 351
 236352        Items.RestoreHeapProperty();
 236353    }
 354
 355    /// <inheritdoc path="//*[not(self::remarks)]"/>
 356    /// <remarks>
 357    /// Just clears the underlying array list.
 358    /// <br/>
 359    /// The internal push timestamp counter is not reset, nor the era. Therefore, new pushes after the clear will
 360    /// receive push timestamps strictly higher than the ones assigned to the items in the queue before the clear.
 361    /// <br/>
 362    /// Time and Space Complexity are O(1).
 363    /// </remarks>
 345364    public virtual void Clear() => Items.Clear();
 365
 366    #endregion
 367
 368    #region Hooks
 369
 370    /// <summary>
 371    /// Invoked just after an item has been pushed into <see cref="Items"/>.
 372    /// </summary>
 373    /// <param name="indexPushed">
 374    /// The index of the item being pushed.
 375    /// <br/>
 376    /// When the heap is at the beginning of the list (which is the layout used by this queue), it is equal to
 377    /// Count - 1 if the underlying list is fully utilized, and it's smaller than that otherwise (there is buffer at
 378    /// the end of the list, after the last item of the heap).
 379    /// </param>
 21008380    protected virtual void RaiseItemPushed(int indexPushed) { }
 381
 382    /// <summary>
 383    /// Invoked just before an item is removed from <see cref="Items"/>.
 384    /// </summary>
 385    /// <param name="indexPopped">
 386    /// The index of the item being popped.
 387    /// <br/>
 388    /// When the heap is at the beginning of the list (which is the layout used by this queue), it is equal to 0.
 389    /// </param>
 390    /// <param name="indexInBufferArea">
 391    /// The index of the item of the last leaf, which is going to be swapped with the root during pop.
 392    /// </param>
 13826393    protected virtual void RaiseItemPopping(int indexPopped, int indexInBufferArea) { }
 394
 395    /// <summary>
 396    /// Invoked just after two items have been swapped of position in <see cref="Items"/>.
 397    /// </summary>
 398    /// <param name="index1">The index of the first item swapped.</param>
 399    /// <param name="index2">The index of the second item swapped.</param>
 95492400    protected virtual void RaiseItemsSwapped(int index1, int index2) { }
 401
 402    #endregion
 403}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

get_CurrentPushTimestamp()
get_Items()
.ctor()
.ctor(MoreStructures.PriorityQueues.BinaryHeap.BinaryHeapPriorityQueue`1<T>)
get_Count()
GetEnumerator()
System.Collections.IEnumerable.GetEnumerator()
Peek()
Pop()
Push(T,System.Int32)
PeekKth(System.Int32)
MergeFrom(MoreStructures.PriorityQueues.BinaryHeap.BinaryHeapPriorityQueue`1<T>)
Clear()
RaiseItemPushed(System.Int32)
RaiseItemPopping(System.Int32,System.Int32)
RaiseItemsSwapped(System.Int32,System.Int32)