Class UpdatableFibonacciHeapPriorityQueue<T>

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

Inheritance
System.Object
BinomialHeapPriorityQueue<T>
FibonacciHeapPriorityQueue<T>
UpdatableFibonacciHeapPriorityQueue<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.FibonacciHeap
Assembly: MoreStructures.dll
Syntax
public sealed class UpdatableFibonacciHeapPriorityQueue<T> : FibonacciHeapPriorityQueue<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 FibonacciHeapPriorityQueue<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
- Both Peek() and UpdatePriority(T, Int32) have constant Time and Space Complexity (update having constant amortized complexity).
- However, Pop() has 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 - FIBONACCI HEAP UPDATE PART
- The algorith behaves quite differently, depending on whether the new priority for the specified item is higher or equal than P, as opposed to when it's lower.
- When the priority is higher or equal and the node is a root, there is no structural change to the heap. The value of priority is updated and the reference to the max priority is checked and potentially updated.
- When the priority is higher or equal and the node is not a root, the node is promoted to a root and its loser flag is reset. If the parent of the node was flagged as a loser, the parent is promoted to root too, and its loser flag is reset as well. That continues up to the first ancestor which is not a loser.
- When the priority is lower, the node is not promoted to a root. Its children are, instead. As in the Pop(), merging and max root reference update take place.
- Finally, the MoreStructures.PriorityQueues.PrioritizedItem<T> before the update is returned as result.

COMPLEXITY - FIBONACCI HEAP UPDATE PART
- The complexity is different depending on the value of new priority for the specified item being higher or equal than the highest in the queue for that item, or lower.
- When the value is bigger or equal than P, Time and Space Complexity are O(1), amortized.
- When the value is smaller than P, Time Complexity and Space Complexity are both O(log(n)). Same analysis as for Pop() applies (since very similar operations are performed).

COMPLEXITY - OVERALL
- When the value is bigger or equal than P, Time Complexity is O(dup_factor) and Space Complexity is O(1), amortized.
- When the value is smaller than P, Time Complexity is O(log(n) + dup_factor) and Space Complexity is O(1).

Implements

IEnumerable<>

Extension Methods