Min Fibonacci HeapCollection of min trees.
The min trees need not be Binomial trees.
Fibonacci Heaps
Remove arbitrary is useful in (for example) correspondence structures.
Single Source All Destinations Shortest Paths
1 2 3 4 5 6 7 2 6 16 7 8 10 3 14 4 4 5 3 1
Greedy Single Source All Destinations
Known as Dijkstra’s algorithm.
Let d(i) be the length of a shortest one edge extension of an already generated shortest path, the one edge extension ends at vertex i.
The next shortest path is to an as yet unreached vertex for which the d() value is least.
After the next shortest path is generated, some d() values are updated (decreased).
Operations On d()
Remove min.
Done O(n) times, where n is the number of vertices in the graph.
Decrease d().
Done O(e) times, where e is the number of edges in the graph.
Array.
O(n2) overall complexity.
Min heap.
O(nlog n + elog n) overall complexity.
Fibonacci heap.
O(nlog n + e) overall complexity.
Prim’s Min-Cost Spanning Tree Algorithm
Array.
O(n2) overall complexity.
Min heap.
O(nlog n + elog n) overall complexity.
Fibonacci heap.
O(nlog n + e) overall complexity.
Min Fibonacci Heap
Collection of min trees.
The min trees need not be Binomial trees.
Node Structure
Degree, Child, Data
Left and Right Sibling
Used for circular doubly linked list of siblings.
Parent
Pointer to parent node.
ChildCut
True if node has lost a child since it became a child of its current parent.
Set to false by remove min, which is the only operation that makes one node a child of another.
Undefined for a root node.
Doubly linked list … remove arbitrary uses external pointers to nodes. So, we cannot copy an element from the next node as is done in the delete of an arbitrary node from a singularly linked circular list. Further, there is a parent pointer to a node. If you move an
element you must change the parent pointer from its children. This would take O(children) time.
Parent field needed for decreaseKey and cascading cut.
Fibonacci Heap Representation
Parent and ChildCut fields not shown. 6 4 9 5 8 7 3 1 9 5 6 5 9 2 8 6 7 4 A
Try to remove 4. If you copy the 5 over, there is an external pointer to 5’s former node
And also a parent pointer from 6 to 5.
Remove(theNode)
theNode points to the Fibonacci heap node that contains the element that is to be removed.
theNode points to min element => do a remove min.
In this case, complexity is the same as that for remove min.
Remove(theNode)
theNode points to an element other than the min element.
Remove theNode from its doubly linked sibling list.
If sibling list becomes empty, make parent’s child pointer null.
Set parent field of theNode’s children to null.
Combine top-level list and children list of theNode; do not pairwise combine equal degree trees.
Free theNode.
In this case, actual complexity is O(log n) (assuming theNode has O(log n) children).
Combine top-level list and children of theNode. 8 7 3 1 6 5 9 2 8 6 7 4 10 4 9 5 6 9 5
Must make parent pointers in theNode’s children equal to null.
Remove(theNode)
8 7 3 1 6 5 9 2 8 6 7 4 10 9 5 6 9 5
DecreaseKey(theNode, theAmount)
If theNode is not a root and new key < parent key, remove subtree rooted at theNode from its doubly linked sibling list.
Insert into top-level list. 8 7 3 1 6 5 9 2 8 6 7 4 10 4 9 5 theNode 6 9 5
DecreaseKey(theNode,4). Actual complexity is O(1). Possible update of min element pointer.
DecreaseKey(theNode, theAmount)
10 0 9 5 8 7 3 1 6 5 9 2 8 6 7 4 6 9 5
Cascading Cut
When theNode is cut out of its sibling list in a remove or decrease key operation, follow path from parent of theNode to the root.
Encountered nodes (other than root) with ChildCut = true are cut from their sibling lists and inserted into top-level list.
Stop at first node with ChildCut = false.
For this node, set ChildCut = true.
Cascading Cut Example
8 7 3 1 6 5 9 2 8 6 7 4 9 9 8 theNode T T F Decrease key by 2.
Comments