Class BinomialHeapPriorityQueue<T>

An IPriorityQueue<T> implementation based on a Binomial Max Heap of its items. It also supports IMergeablePriorityQueue<T, TPQTarget> operations.

Inheritance

System.Object

BinomialHeapPriorityQueue<T>

UpdatableBinomialHeapPriorityQueue<T>

FibonacciHeapPriorityQueue<T>

Implements

IMergeablePriorityQueue<T, BinomialHeapPriorityQueue<T>>

IPriorityQueue<T>

IEnumerable<T>

Inherited Members

System.Object.Equals(System.Object)

System.Object.Equals(System.Object, System.Object)

System.Object.GetHashCode()

System.Object.GetType()

System.Object.MemberwiseClone()

System.Object.ReferenceEquals(System.Object, System.Object)

System.Object.ToString()

Namespace: MoreStructures.PriorityQueues.BinomialHeap

Assembly: MoreStructures.dll

Syntax

public class BinomialHeapPriorityQueue<T> : IMergeablePriorityQueue<T, BinomialHeapPriorityQueue<T>>, IPriorityQueue<T>

Type Parameters

Name	Description
T

Remarks

DEFINITION
- A Binomial Heap is a forest of n-ary trees, each respecting the heap max property, having a binomial layout and unicity of degree.
- A tree respects the heap max property when each node has a value to be non-smaller than all its children (and, by transitivity, its grand-children, grand-grand-children etc.).
- A tree has a binomial layout when is in the set of tree defined in the following constructive way: a singleton tree is a binomial tree of degree 0, a binomial tree of degree k + 1 is obtained merging two binomial trees of degree k, so that the root of one becomes immediate child of the root of the other.
- A tree has unicity of degree when it is the only tree in the forest having its degree, which is the number of children it has. That means that there can be a single tree with 0 children (singleton), a single tree with 1 child, etc.

ADVANTAGES AND DISADVANTAGES
- This heap implementation is conceptually extending BinaryHeapPriorityQueue<T>, making heaps easily mergeable (i.e. in less time than O(n).
- Binary Heaps provide logarithmic insertion and extraction. They can also provide linear construction, when the data is provided in batch and not online.
- However, Binary Heap have O(n * log(n)) Time Complexity in merge. Merging the smaller heap into the bigger one, in the worst case the two heaps being merged have comparable size n / 2, resulting into an overall O(n / 2 * log(n / 2)) = O(n * log(n)) Time Complexity.
- Merging the underlying arrays and building the new Binary Heap in batch would improve performance, yielding O(n) Time Complexity. Still an expensive operation, as it means going through all elements of one heap.
- Binomial Heaps overcome this limitation and offer sub-linear performance by taking advantage of both the linked list layout and the tree layout, and taking the best of both worlds.
- So the underlying idea behind Binomial Heaps is to combine linked lists and trees, and represent the data as a forest of n-ry heap trees (respecting the binomial layout), which can be easily merged together into a single Binomial Heap, due to their "recurrent" structure.
- While Push(T, Int32) and Pop() retain logarithmic complexity, merging also becomes a logarithmic operation.

Constructors

BinomialHeapPriorityQueue()

Builds an empty priority queue.

Declaration

public BinomialHeapPriorityQueue()

BinomialHeapPriorityQueue(BinomialHeapPriorityQueue<T>)

Builds a deep, separate copy of the provided source priority queue.

Declaration

protected BinomialHeapPriorityQueue(BinomialHeapPriorityQueue<T> source)

Parameters

Type	Name	Description
BinomialHeapPriorityQueue<T>	source	The priority queue to be copied over.

Remarks

Doesn't copy the items themselves, it only deep-copies the internal structure of the source queue.
Warning: push timestamp eras are shared between items of the two queues! To be used only for GetEnumerator() support.

Properties

Count

Declaration

public virtual int Count { get; }

Property Value

Type	Description
System.Int32

Remarks

Checks the count internally stored, keeping track of the sum of the size of all trees in the linked list.
Time and Space Complexity are O(1).

CurrentPushTimestamp

A non-negative, zero-based, monotonically strictly increasing counter, incremented at every insertion into this data structure by a Push(T, Int32).

Declaration

protected int CurrentPushTimestamp { get; set; }

Property Value

Type	Description
System.Int32

ItemsCount

The total number of items in this queue.

Declaration

protected int ItemsCount { get; set; }

Property Value

Type	Description
System.Int32

MaxRootsListNode

Reference to the tree root in the forest with the highest priority. Makes Peek O(1).

Declaration

protected LinkedListNode<TreeNode<T>>? MaxRootsListNode { get; set; }

Property Value

Type	Description
System.Nullable<LinkedListNode<TreeNode<T>>>

PushTimestampEras

The eras in which all push timestamps created by this instance (e.g. on push), or merged into this instance, leave in. The last in the list is the current one.

Declaration

protected IList<PushTimestampEra> PushTimestampEras { get; }

Property Value

Type	Description
System.Collections.IList<PushTimestampEra>

Remarks

By default, initialized to a singleton list containing the era "0".
Depending on the implementation, may be relevant in merging.

Roots

A of all the roots of the forest representing the heap.

Declaration

protected LinkedList<TreeNode<T>> Roots { get; }

Property Value

Type	Description
MoreStructures.PriorityQueues.LinkedList<TreeNode<T>>

Methods

AddRoot(TreeNode<T>)

Adds a brand new TreeNode<T> to the heap, as a new root in the forest.

Declaration

protected void AddRoot(TreeNode<T> newRoot)

Parameters

Type	Name	Description
TreeNode<T>	newRoot	The new root.

AttachToRoots(TreeNode<T>)

Attaches the provided TreeNode<T> to the Roots.

Declaration

protected LinkedListNode<TreeNode<T>> AttachToRoots(TreeNode<T> newRoot)

Parameters

Type	Name	Description
TreeNode<T>	newRoot	A node with no parent, and not already a root.

Returns

Type	Description
LinkedListNode<TreeNode<T>>	The of Roots pointing to the newRoot.

Clear()

Declaration

public virtual void Clear()

Remarks

First, calls RaiseItemsClearing().
Then, removes all the trees from the forest, reset to the items count to 0 and set the reference to the max priority root to null.
The internal push timestamp counter is not reset, nor the era. Therefore, new pushes after the clear will receive push timestamps strictly higher than the ones assigned to the items in the queue before the clear.
Time and Space Complexity are O(1), with RaiseItemsClearing() assumed to be O(1).

DetachFromRoots(LinkedListNode<TreeNode<T>>)

Detaches the TreeNode<T> pointed by the provided rootsListNode from the Roots.

Declaration

protected TreeNode<T> DetachFromRoots(LinkedListNode<TreeNode<T>> rootsListNode)

Parameters

Type	Name	Description
LinkedListNode<TreeNode<T>>	rootsListNode	The of Roots, pointing to the TreeNode<T> root.

Returns

Type	Description
TreeNode<T>	The detached TreeNode<T> root.

GetEnumerator()

Declaration

public virtual IEnumerator<T> GetEnumerator()

Returns

Type	Description
System.Collections.IEnumerator<T>

Remarks

In order to return items in heap order (i.e. the max at each step), it first copies this priority queue into a second temporary queue, which can be mutated without affecting the state of this queue.
It then iterates over the copy, calling Pop() until it becomes empty.
Time Complexity is O(n * log(n)) (when fully enumerated), because a single Pop() on a Binomial Heap takes logarithmic time, and there are n items to be extracted.
Space Complexity is O(n), as a copy of this queue is required as auxiliary data structure to emit elements in the right order of priority.

MergeEquiDegreeTrees()

Merges all trees of the Roots forest with the same degree (number of children of the root).

Declaration

protected virtual void MergeEquiDegreeTrees()

MergeFrom(BinomialHeapPriorityQueue<T>)

Declaration

public virtual void MergeFrom(BinomialHeapPriorityQueue<T> targetPriorityQueue)

Parameters

Type	Name	Description
BinomialHeapPriorityQueue<T>	targetPriorityQueue

Remarks

ALGORITHM
- Before the actual merge of roots, push timestamp eras need to be adjusted, to deal with potentially conflicting timestamps from the two queues without scanning through all items, which would take a linear amount of time.
- In order to do so, the max push timestamp era M, between the current era of the source and the current era of the target (the last in the list of eras of each), is calculated.
- Then, all the push timestamp eras of the target are mutated (i.e. by a set accessor on the instance) in order (from the first = the older, to the last = the most recent) to M + 1, M + 2, ...
- This way all items of the target are considered as added after all current items of the source, and keep the order they had in the target between themselves, before the merge.
- Then, a new current push timestamp era of the source is added (i.e. new instance) with a new push timestamp era set to M + N + 1, so that all items of the source coming after the merge are considered as added after all items of the target added during merge.
- After that, the algorithm iterates over all the roots of the target heap.
- Add each root R to the linked list of roots of the source heap and increases the total items count of the source heap by the number of items in R, which can be calculated without traversing, from the number of immediate children c of R as 2^c, being R a binomial tree. tree.
- For each added root, RaiseRootMerged(TreeNode<T>) is invoked.
- Then binomial heap shape is restored by merging together all trees with the same degree and a new linear scan of the root is done, to update the reference to the root with highest priority, exactly as in Push(T, Int32) and Pop().
- To separate avoid interferences between this queue and the targetPriorityQueue, the targetPriorityQueue is cleared of all its items.
- Its current push timestamp is left unchanged and the push timestamp eras are cleared and set to a new single instance with the same era value it had before the merge. This way all new items in the targetPriorityQueue will share the reference to the new era object, and wont interfere with the era object of all items moved to this priority queue.

COMPLEXITY
- For this analysis, events, and in particular RaiseRootMerged(TreeNode<T>), are considered O(1) both in Time and Space Complexity.
- The number of roots of the target heap is logarithmic with the number m of items in the target heap.
- Adding each root R of the target heap to the forest of the source heap and increasing the items count are both constant-time operations.
- Housekeeping operations, done after that on the source heap, take logarithmic time, as explained in Pop().
- Clearing the target is also a constant-time operation.
- Therefore, Time and Space Complexity are O(log(m)).

MergeRoots(LinkedListNode<TreeNode<T>>, LinkedListNode<TreeNode<T>>)

Merges the two provided trees of the forest into a single one, preserving the heap property.

Declaration

protected LinkedListNode<TreeNode<T>> MergeRoots(LinkedListNode<TreeNode<T>> first, LinkedListNode<TreeNode<T>> second)

Parameters

Type	Name	Description
LinkedListNode<TreeNode<T>>	first	The of Roots pointing to the root of the first tree to merge.
LinkedListNode<TreeNode<T>>	second	The of Roots pointing to the root of the second tree to merge.

Returns

Type	Description
LinkedListNode<TreeNode<T>>	The of Roots pointing to the root of the merged tree: either first or second, depending on the MoreStructures.PriorityQueues.PrioritizedItem<T> stored in the PrioritizedItem of .

Peek()

Declaration

public virtual PrioritizedItem<T> Peek()

Returns

Type	Description
MoreStructures.PriorityQueues.PrioritizedItem<T>

Remarks

Peeks the item of the linked list pointed by the "max root" internal property.
By transitivity, the item of the max root contains the max item in the queue, since all roots are non-smaller than their descendants.
Therefore, Time and Space Complexity are O(1).

Pop()

Declaration

public virtual PrioritizedItem<T> Pop()

Returns

Type	Description
MoreStructures.PriorityQueues.PrioritizedItem<T>

Remarks

ALGORITHM
- The value of the tree root with highest priority is read, then the root is removed from the forest.
- The orphan children of the removed root are promoted to being roots and added to the forest.
- Then all trees with the same degree are merged together, where the root with lower priority becomes immediate child of the root with higher priority.
- Merging is done efficiently by linearly scanning all the tree roots in the forest, and keeping an array A of tree roots indexed by their degree.
- Every time a second tree with the same degree is encountered: if T1 has degree k and A[k] already references another tree T2 with degree k, T1 and T2 are merged into a tree whose root has degree k + 1, A[k] is reset and A[k + 1] is set.
- After all equi-degree trees have been merged, a new linear scan of the root is done, to update the reference to the root with highest priority.

COMPLEXITY
- Removing the root with highest priority from the forest is a O(1) operation.
- Promoting to roots all its children is proportional to the number of children, a root of the forest has.
- In a Binomial Heap the max degree of the roots of the forest is logarithmic with the total number of items in the heap. Therefore, promotion of children to roots is a O(log(n)) operation.
- Merging equi-degree trees requires a full scan of the roots in the forest. If the forest were made of a lot of shallow trees, that would result into a O(n) operation.
- However, while Push(T, Int32) increases every time by 1 the count of trees, after n insertions in O(1), a single O(n) scan done by a Pop() would merge trees, making them logarithmic in number.
- Updating the max root reference takes time proportional to the number of trees in the forest AFTER the merging.
- Because the merging of equi-degree trees leaves a forest of trees all of different degrees, and the max degree is logarithmic with n, at the end of the merging procedure there can be at most a logarithmic number of different trees in the forest.
- So the linear scan of tree roots in the forest to find the max root reference takes only a logarithmic amount of time.
- Therefore, Time Complexity is O(log(n)). Space Complexity is also O(log(n)), since merging equi-degree trees requires instantiating an array index by degrees, and max degree is O(log(n)).

PromoteChildToRoot(TreeNode<T>)

Promotes the provided TreeNode<T>, to being a root, detaching it from its current parent.

Declaration

protected virtual void PromoteChildToRoot(TreeNode<T> child)

Parameters

Type	Name	Description
TreeNode<T>	child	A child of a node of a tree in the forest.

Push(T, Int32)

Declaration

public virtual void Push(T item, int priority)

Parameters

Type	Name	Description
T	item
System.Int32	priority

Remarks

ALGORITHM
- Adds a new singleton tree T (degree 0) to the forest, wrapping the provided item with its priority into an object R with no children, and wrapping R into a LLN, which represents the root of T.
- Then all trees with the same degree are merged together, with the same procedure explained in the documentation of Pop().
- That ensures that the binomial shape of the forest (i.e. binomial trees all of different degrees) is preserved. Without merging, if a tree of degree 0 (i.e. a singleton tree) was already present before the push of the new root, the binomial heap property would have been violated.
- After all equi-degree trees have been merged, a new linear scan of the root is done, to update the reference to the root with highest priority (so that Peek() will work correctly and in constant time).

COMPLEXITY
- Adding a new root to the forest of trees is a constant-time operation, since the root is added at the end of the linked list representing the forest, which keeps references to both ends of the chain of nodes.
- Merging equi-degree trees, to restore the binomial shape of the heap forest, and updating the max root reference are both logarithmic operations in time. The merge also requires a space proportional to the logarithm of the number of items in the heap, to instantiate its data structure.
- Check the complexity analysis of Pop() for further details.
- Therefore, Time and Space Complexity are both O(log(n)).

RaiseItemPopping(TreeNode<T>)

Invoked just before an item is removed from the heap.

Declaration

protected virtual void RaiseItemPopping(TreeNode<T> root)

Parameters

Type	Name	Description
TreeNode<T>	root	The TreeNode<T> about to be removed from the heap.

RaiseItemPushed(TreeNode<T>)

Invoked just after an item has been pushed into the heap (as a root).

Declaration

protected virtual void RaiseItemPushed(TreeNode<T> newRoot)

Parameters

Type	Name	Description
TreeNode<T>	newRoot	The TreeNode<T> added to the heap.

Remarks

Not invoked on merging, for which RaiseRootMerged(TreeNode<T>) is invoked instead.

RaiseItemsClearing()

Invoked just before the all the items in the heap are wiped out.

Declaration

protected virtual void RaiseItemsClearing()

RaiseRootMerged(TreeNode<T>)

Invoked just after an heap tree has been added to the forest (root and all its descendants).

Declaration

protected virtual void RaiseRootMerged(TreeNode<T> root)

Parameters

Type	Name	Description
TreeNode<T>	root	The root TreeNode<T> of the heap tree added to the forest.

UpdateMaxRootsListNode()

Performs a linear scan of the roots and update the MaxRootsListNode with a reference to the root of max priority.

Declaration

protected void UpdateMaxRootsListNode()

UpdateMaxRootsListNodeAfterRootNewOrIncrease(LinkedListNode<TreeNode<T>>)

Updates the reference to the max priority root to the provided rootsListNode, if that root has a higher priority than the value of the current max priority root.

Declaration

protected void UpdateMaxRootsListNodeAfterRootNewOrIncrease(LinkedListNode<TreeNode<T>> rootsListNode)

Parameters

Type	Name	Description
LinkedListNode<TreeNode<T>>	rootsListNode	The root whose priority has been increased.

Explicit Interface Implementations

IEnumerable.GetEnumerator()

Declaration

IEnumerator IEnumerable.GetEnumerator()

Returns

Type	Description
System.Collections.IEnumerator

Remarks

Implements

IMergeablePriorityQueue<T, TPQTarget>

IPriorityQueue<T>

IEnumerable<>

Extension Methods

SuffixStructureNodeExtensions.GetAllSuffixesFor<TEdge, TNode>(TNode, TextWithTerminator)

UpdatablePriorityQueueExtensions.PopAll<T>(IPriorityQueue<T>)