A Fibonacci heap is a specific implementation of the heap data structure that makes use of Fibonacci numbers. Fibonacci heaps are used to implement the priority queue element in Dijkstra’s algorithm, giving the algorithm a very efficient running time.
Fibonacci heaps have a faster amortized running time than other heap types. Fibonacci heaps are similar to binomial heaps but Fibonacci heaps have a less rigid structure. Binomial heaps merge heaps immediately but Fibonacci heaps wait to merge until the
extract-min function is called. While Fibonacci heaps have very good theoretical complexities, in practice, other heap types such as pairing heaps are faster. This is because even in the simplest implementation, Fibonacci heaps require four pointers for each node, other heaps need two or three.
As the name suggests, Fibonacci heaps use Fibonacci numbers in its structure.
The Fibonacci numbers are the terms of a sequence of integers in which each term is the sum of the two previous terms with
The first few Fibonacci numbers are
Like binomial heaps, Fibonacci heaps use doubly linked lists to allow for time for operations such as splicing off a part of a list, merging two lists, and finding the minimum (or maximum) value. Each node contains a pointer to its parent and any one of its children. The children are all linked together in a doubly linked list called the child list. Each child in the child list has pointers for its left sibling and its right sibling.
For each node, the linked list also maintains the number of children a node has, a pointer to the root containing the minimum key, and whether the node is marked. A node is marked to indicate that it has lost a single child and a node is unmarked if it loses no children. See the description of the
decrease-key function in the next section for more details.
Here is an image showing the differences between a singly linked list and a doubly-linked list. The singly linked has only one pointer from each node, while the doubly linked has pointers going both to and from a node.
In Fibonacci heaps, the degrees of nodes (the number of children) are constrained. Each node in the heap has degree at most , and the size of a subtree rooted in a node of degree is at least , where is the kth Fibonacci number. This structure is maintained by having a rule that at most one child can be cut from each non-root node. When a second child is removed, the node itself needs to be removed from its parent and becomes the root of a new tree. This means that the number of trees is decreased in the operation
extract-min, where trees are linked together.
Fibonacci heaps must satisfy the min-heap property (or max-heap property if making a max-heap) where every node’s children must have a smaller value than it (the parent), and therefore, the minimum element will always be at the root of one of the trees.
Here is how Fibonacci heaps implement the basic functionalities of heaps and the time complexity of each operation. The children of each node are also related using a linked list. For each node, the linked list maintains the number of children a node has and whether the node is marked. The linked list also maintains a pointer to the root containing the minimum key. A node is marked to indicate if any of its children were removed. This is important so the heap can keep track of how far removed its shape is becoming from a binomial heap. If a Fibonacci heap is too different from a binomial heap, it loses many of the efficient time operations that their binomial nature gives it.
These operations are described in terms of a min Fibonacci heap, but they could easily be adapted to be max Fibonacci heap operations.
The linked list has pointers and keeps track of the minimum node, so finding the minimum is simple and can be done in constant time.
In Fibonacci heaps, merging is accomplished by simply concatenating two lists containing the tree roots. Compare the roots of the two heaps to be merged, and whichever is smaller becomes the root of the new combined heap. The other tree is added as a subtree to this root. This can be done in constant time.
Explain why Fibonacci heaps allow for constant time merging. What does this mean for the
insertoperation?Concatenating the two lists can be done in constant time. Doing operations to a linked list is constant time since it is just a matter of updating pointers. Comparing the roots of two heaps is also constant time.
insertis just taking the node to be inserted and treating it like a heap to be merged with the heap we are inserting the node into, we just call
mergeon the two. This means that
insertis also constant time.
extract-min is one of the most important operations regarding Fibonacci heaps. Much of a Fibonacci heap’s speed advantage comes from the fact that it delays consolidating heaps after operations until
extract-min is called. Binomial heaps, on the other hand, consolidate immediately. Consolidation occurs when heap properties are violated, for example, if two heaps have the same order, the heaps must be adjusted to prevent this.
Deleting the minimum element is done in three steps. The node is removed from the root list and the node’s children are added to the root list. Next, the minimum element is updated if needed. Finally, consolidate the trees so that there are no repeated orders. If any consolidation occurred, make sure to update the minimum element if needed. Delyaing consolidation saves times.
The two images below show the
extract-min function on the Fibonacci heap shown in the introduction.
Insertion to a Fibonacci heap is similar to the
insert operation of a binomial heap. A heap of one element is created and the two heaps are merged with the
merge function. The minimum element pointer is updated if necessary. The total number of nodes in the tree increases by one.
To delete an element, decrease the key using
decrease key to negative infinity, and then call
extract-min. When the node has a value of negative infinity, since the heap is a min heap, it will become the root of the tree.
extract-min will remove the top element, so doing this deletes the node in question.
There are two situations that can arise when decreasing the key: the change will cause a heap violation or it will not.
If the heap properties aren’t violated, simply decrease .
If a violation does occur, remove the node its parent. If the parent is not a root, mark it. If it has been marked already, it is removed as well and its parent is marked, and so on. Continue this process up the tree until either the root or an unmarked node is reached. Next, set the minimum pointer to the decreased value if it is the new minimum.
The decrease key function marks a node when its child is removed. This allows it to track some history about each node. Essentially the marking tracks if:
- The node has had no children removed (unmarked)
- The node has had a single child removed (marked)
- The node is about to have a second child removed (removing a child of a marked node)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
Python implementations of Fibonacci heaps can be quite long, but here is an example Python implementation.
|Operation||Amortized Running Time|
According to a paper written by Michael Fredman (one of the inventors of Fibonacci heaps), Fibonacci heaps have a couple of downsides: many computer scientists claim that they are difficult to program and their theoretically excellent running times aren't always better in practice than theoretically inferior types of heaps.
- , . Fibonacci_Heap. Retrieved June 25, 2016, from https://en.wikipedia.org/wiki/Fibonacci_heap
- , B. Fibonacci_Heap. Retrieved June 7, 2016, from https://en.wikipedia.org/wiki/File:Fibonacci_heap.png
- , L. Doubly-linked-list.svg. Retrieved June 25, 2016, from https://en.wikipedia.org/wiki/File:Doubly-linked-list.svg
- , L. Singly-linked-list.svg. Retrieved June 25, 2016, from https://en.wikipedia.org/wiki/File:Singly-linked-list.svg
- , . Fibonacci heap. Retrieved June 7, 2016, from https://en.wikipedia.org/wiki/Fibonacci_heap
- , M. Fibonacci heap extractmin1.png. Retrieved June 7, 2016, from https://en.wikipedia.org/wiki/File:Fibonacci_heap_extractmin1.png
- , B. Fibonacci heap extractmin2.png. Retrieved June 7, 2016, from https://en.wikipedia.org/wiki/File:Fibonacci_heap_extractmin2.png
- , B. Fibonacci heap-decreasekey.png. Retrieved June 7, 2016, from https://en.wikipedia.org/wiki/File:Fibonacci_heap-decreasekey.png
- Imms, D. Fibonacci Heap. Retrieved June 7, 2016, from http://www.growingwiththeweb.com/2014/06/fibonacci-heap.html
- Stergiopoulos , S. Algorithm for Fibonacci Heap Operations. Retrieved June 7, 2016, from http://www.cse.yorku.ca/~aaw/Sotirios/BinomialHeapAlgorithm.html
- Cormen, T., Leiserson, C., Rivest, R., & Stein, C. (2001). Introduction to Algorithms (2nd edition) (pp. chapter 20). The MIT Press.
- Fredman, M., Sedgewick, R., Sleator, D., & Tarjan, R. The Pairing Heap: A New Form of Self-Adjusting Heap. Retrieved June 7, 2016, from https://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf