Class FibonacciHeapPriorityQueue<T>
An IPriorityQueue<T> implementation based on a Fibonacci Max Heap of its items.
Inheritance
Implements
Inherited Members
Namespace: MoreStructures.PriorityQueues.FibonacciHeap
Assembly: MoreStructures.dll
Syntax
public class FibonacciHeapPriorityQueue<T> : BinomialHeapPriorityQueue<T>, IMergeablePriorityQueue<T, BinomialHeapPriorityQueue<T>>, IPriorityQueue<T>Type Parameters
| Name | Description |
|---|---|
| T |
Remarks
DEFINITION
- A Fibonacci Heap is a Binomial Heap which has its heap max property and binomial
layout invariants always satisfied, but can have unicity of degree temporarily invalidated
(until next Pop() operation).
- Nodes of the heaps can be flagged as losers, meaning that they have lost at least once a children,
after its promotion to being a new root.
ADVANTAGES AND DISADVANTAGES
- This heap implementation is a Binomial Heap refinement which prioritises performance of Push(T, Int32)
and update operations over Pop().
- It does so by taking advantage of both the linked list layout and the tree layout, pretty much like
Binomial Heaps.
- Implementations based on linked or array lists are really fast at insertion, because they don't internally
keep the data sorted. However, extraction becomes expensive, for the very same reason that data is unsorted.
- At the other end of the spectrum, trees are logarithmic at insertion, because they have to keep data at least
partially sorted, at all time. Extraction, however, is very cheap.
- So the underlying idea behind Fibonacci Heaps is to combine linked lists and trees, and represent the data as
a forest of n-ry heap trees, exactly like Binomial Heaps, and exploit the easy insertion in linked list
(which is not implemented by the standard Push into a Binomial Heap).
- In doing so, both Push(T, Int32) and update becomes extremely fast, running in O(1) and O(1)
amortized, respectively.
- However, unlike ArrayListPriorityQueue<T>,
Pop() doesn't become a O(n) operation. Instead, it retains
logarithmic runtime.
- This proves to be the best compromise for applications such as the Dijkstra algorithm (implemented in
DijkstraShortestDistanceFinder), which uses a priority queue to find
the next best vertex.
- Dijkstra algorithm performs O(e) PushOrUpdate<T>(IUpdatablePriorityQueue<T>, T, Int32)
operations and O(v) Pop() operations, where e and v are the number
of edges and vertices in the graph, respectively.
- In dense graphs e is O(v^2), so the number of push/update operations is way higher than the number of pop
operations, and it makes sense to optimize the former, at the cost of the latter.
Constructors
| Improve this Doc View SourceFibonacciHeapPriorityQueue()
Builds an empty priority queue.
Declaration
public FibonacciHeapPriorityQueue()FibonacciHeapPriorityQueue(FibonacciHeapPriorityQueue<T>)
Builds a deep, separate copy of the provided source priority queue.
Declaration
protected FibonacciHeapPriorityQueue(FibonacciHeapPriorityQueue<T> source)Parameters
| Type | Name | Description |
|---|---|---|
| FibonacciHeapPriorityQueue<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.
Methods
| Improve this Doc View SourceGetEnumerator()
Declaration
public override IEnumerator<T> GetEnumerator()Returns
| Type | Description |
|---|---|
| IEnumerator<T> |
Overrides
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 Fibonacci 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.
PromoteChildToRoot(TreeNode<T>)
Promotes the provided TreeNode<T>, to being a root, detaching it from its current parent. Also, resets the "loser" flag of the child (behavior specific to Fibonacci Heaps).
Declaration
protected override void PromoteChildToRoot(TreeNode<T> child)Parameters
| Type | Name | Description |
|---|---|---|
| TreeNode<T> | child | A child of a node of a tree in the forest. |
Overrides
Push(T, Int32)
Declaration
public override void Push(T item, int priority)Parameters
| Type | Name | Description |
|---|---|---|
| T | item | |
| System.Int32 | priority |
Overrides
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
- If LLN has higher priority than the root with max priority, updates the reference to the root with max
priority, to point to LLN.
- Unlike Push(T, Int32), it doesn't perform any rebalancing of
the forest just yet, meaning that the binomial property may be temporarily violated until the next
Pop() operation.
- The delay of "housekeeping" operations to restore the shape property of a binomial heap, and the grouping
of such "housekeeping" operations into a single batch, executed at the next
Pop(), is one of the core efficiency mechanisms of the
Fibonacci Heap.
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.
- Therefore, Time Complexity and Space Complexity are O(1).
- Notice that this operation executes in constant time at the cost of adding a new shallow tree to the
forest. After n Push(T, Int32) consecutive operations, the forest would be made of n trees
of degree 0, which is the shape of a simple heap based on a linked list.
- This cost has to be beared by Pop(), which runs in logarithmic
time but merges trees of the same degree and does so in batch.