Class UpdatableBinomialHeapPriorityQueue<T>

A refinement of BinomialHeapPriorityQueue<T> which supports IUpdatablePriorityQueue<T> operations, such as retrieval and update of priorities and removal of items.

Inheritance
System.Object
BinomialHeapPriorityQueue<T>
UpdatableBinomialHeapPriorityQueue<T>
Implements
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 sealed class UpdatableBinomialHeapPriorityQueue<T> : BinomialHeapPriorityQueue<T>, IMergeablePriorityQueue<T, BinomialHeapPriorityQueue<T>>, IUpdatablePriorityQueue<T>, IPriorityQueue<T>
Type Parameters
Name Description
T
Remarks

Check DuplicatedItemsResolution<TItems, THeap> for detailed informations about how the mapping between items of type T and heap nodes of type TreeNode<T> is performed, in presence of duplicates.

Methods

| Improve this Doc View Source

Clear()

Declaration
public override void Clear()
Overrides
MoreStructures.PriorityQueues.BinomialHeap.BinomialHeapPriorityQueue<T>.Clear()
Remarks

Clears the BinomialHeapPriorityQueue<T> structures and the additional DuplicatedItemsResolution<TItems, THeap> object introduced to support updates and deletions.
Time and Space Complexity is O(1).

| Improve this Doc View Source

GetPrioritiesOf(T)

Declaration
public IEnumerable<int> GetPrioritiesOf(T item)
Parameters
Type Name Description
T item
Returns
Type Description
IEnumerable<System.Int32>
Remarks

| Improve this Doc View Source

RaiseItemPopping(TreeNode<T>)

Declaration
protected override void RaiseItemPopping(TreeNode<T> root)
Parameters
Type Name Description
TreeNode<T> root
Overrides
MoreStructures.PriorityQueues.BinomialHeap.BinomialHeapPriorityQueue<T>.RaiseItemPopping(MoreStructures.PriorityQueues.BinomialHeap.TreeNode<T>)
Remarks

Hands over to RaiseItemPopping(TreeNode<TItems>).

| Improve this Doc View Source

RaiseItemPushed(TreeNode<T>)

Declaration
protected override void RaiseItemPushed(TreeNode<T> newRoot)
Parameters
Type Name Description
TreeNode<T> newRoot
Overrides
MoreStructures.PriorityQueues.BinomialHeap.BinomialHeapPriorityQueue<T>.RaiseItemPushed(MoreStructures.PriorityQueues.BinomialHeap.TreeNode<T>)
Remarks

Hands over to RaiseItemPushed(TreeNode<TItems>).

| Improve this Doc View Source

Remove(T)

Declaration
public PrioritizedItem<T>? Remove(T item)
Parameters
Type Name Description
T item
Returns
Type Description
System.Nullable<MoreStructures.PriorityQueues.PrioritizedItem<T>>
Remarks

ALGORITHM
- It first retrieves the max priority P from the max priority item the queue via Peek().
- Then, it updates the priority of the provided item via UpdatePriority(T, Int32), setting it to P + 1 and making item the one with max priority.
- Finally it pops the item via Pop().

COMPLEXITY
- Peek() has constant Time and Space Complexity.
- However, Pop() and UpdatePriority(T, Int32) have logarithmic Time Complexity.
- Therefore, Time Complexity is O(log(n) + dup_factor) and Space Complexity is O(1).

| Improve this Doc View Source

UpdatePriority(T, Int32)

Declaration
public PrioritizedItem<T> UpdatePriority(T item, int newPriority)
Parameters
Type Name Description
T item
System.Int32 newPriority
Returns
Type Description
MoreStructures.PriorityQueues.PrioritizedItem<T>
Remarks

ALGORITHM - BINOMIAL HEAP UPDATE PART
- When the priority is higher or equal, the value of priority is updated and the node is sifted up the tree, until the heap property is restored. If the root of the tree is reached, the reference to the max priority is checked and potentially updated.
- When the priority is lower, the value of priority is updated and the node is sifted down the tree, until the heap property is restored. If the node was a root, a linear scan of all the roots is made, to update the reference to the max priority, which may have changed due to the decrease in priority.
- No merging is required, since no node has been added or removed from any of the tree of the heap forest. Nodes have been swapped by sift up or sift down procedures, but the shape of each tree, and so the layout of the forest, hasn't changed. Therefore the binomial heap shape hasn't been violated.
- Finally, the MoreStructures.PriorityQueues.PrioritizedItem<T> before the update is returned as result.

COMPLEXITY - BINOMIAL HEAP UPDATE PART
- Sift up, sift down and linear scan of roots are all logarithmic operations in time and constant in space.
- Therefore, Time Complexity is O(log(n)) and Space Complexity is O(1).

COMPLEXITY - OVERALL
- Time Complexity is O(log(n) + dup_factor) and Space Complexity is O(1).
- Notice how this is higher than the Time Complexity for the corresponding functionality in a Fibonacci Heap, which supports both pushing and priority updating in constant time.

Implements

IEnumerable<>

Extension Methods