This answer will be quite long, but I hope it helps to understand where the Fibonacci bunch came from. I assume you are already familiar with binomial heaps and amortized analysis .
Motivation: Why Fibonacci Heaps?
Before jumping into Fibonacci heaps, it might be useful to research why we even need them in the first place. There are many other types of heaps ( binary heaps and binomial heaps , for example), so why do we need another?
The main reason is the Dijkstra algorithm and the Prim algorithm . Both of these graph algorithms work by supporting priority queue storage nodes with corresponding priorities. Interestingly, these algorithms rely on a heap operation called a decreasing key that takes an entry already in the priority queue and then decreases its key (i.e., increases its priority). In fact, most of the execution time of these algorithms is explained by the number of times you call the decrease key. If we could build a data structure that optimizes the shortcut key, we could optimize the performance of these algorithms. In the case of the binary heap and the binomial heap, the decrease key takes O (log n) time, where n is the number of nodes in the priority queue. If we could drop it by O (1), then the time complexity of Dijkstra's algorithm and Prim's algorithm will move from O (m log n) to (m + n log n), which is asymptotically faster than before. Therefore, it makes sense to try to create a data structure that effectively supports shrinking.
There is another reason to consider creating a better heap structure. When adding elements to an empty binary heap, each insert takes O (log n) time. It is possible to build a binary heap in time O (n) if we know all n elements in advance, but if the elements enter the stream, this is not possible. In the case of a binomial heap, inserting n consecutive elements takes on amortized time O (1) each, but if the inserts alternate with deletions, the inserts may eventually take & Omega; (log n) times each. Therefore, we may need to search for the implementation of the priority queue, which optimizes the inserts to obtain O (1) time each.
Step One: Lazy Binomial Heaps
To start building the Fibonacci heap, we start with the binomial heap and modify it so that the inserts require O (1) time. Not everyone is so unreasonable to try this - after all, if we are going to make a lot of investments and not so many turns, it makes sense to optimize the inserts.
If you remember, binomial heaps work by storing all items on the heap in a collection of binomial trees . A binomial tree of order n has 2 n nodes in it, and a heap is a structure as a collection of binomial trees that all obey the heap property. Typically, the insertion algorithm in a binomial heap works as follows:
- Create a new singleton node (this is a tree of order 0).
- If there is a tree of order 0:
- Combine two trees of order 0 together in a tree of order 1.
- If there is a tree of order 1:
- Combine two trees of order 1 together in tree order 2.
- If there is a tree of order 2:
- ...
This process ensures that at any given time there is no more than one tree of each order. Since each tree contains an exponentially larger number of nodes than its order, this ensures that the total number of trees is small, which allows us to quickly run dequeues (because we do not need to look at too many different trees after the dequeue-min step).
However, this also means that the worst execution time for inserting a node into the binomial heap is & Theta; (log n) because we can have trees & Theta; (log n) to be combined together. These trees should be combined with each other only because we need the number of trees to be low when performing the dequeue stage, and there are no advantages in future inserts to maintain a minimum number of trees.
This introduces the first departure from binomial heaps:
Modification 1 : When inserting a node into the heap, just create a tree of order 0 and add it to the existing tree collection. Do not combine trees together.
There is one more change we can make. Usually, when we combine two binomial heaps, we take a merge step to combine them together in such a way as to ensure that the resulting tree has no more than one tree of each order. Again, we do this compression so that the detectors are fast and there is no real reason why the merge operation would have to pay for it. Therefore, we will make the second change:
Modification 2 : When combining two heaps together, simply merge all their trees together without merging. Do not combine trees together.
If we make this change, we will pretty easily get O (1) performace in our enqueue operations, since all we do is create a new node and add it to the tree collection. However, if we just make this change and do nothing, we will completely ruin the performance of the dequeue-min operation. Recall that dequeue-min needs to be scanned by the roots of all trees in the heap after deleting the minimum value so that it can find the smallest value. If we add to & Theta; (n) the nodes, inserting them in the path, our dequeue operation will then have to spend & theta; (n) time looking through all these trees. This is a huge performance ... can we avoid it?
If our inserts really just add more trees, then the first dequeue we make will certainly take & Omega; (n) time. However, this does not mean that every detective must be expensive. What happens if, after executing dequeue, we merge all the trees on the heap together, so that we end up with only one tree of each order? It will take a lot of time, but if we start several times in a row, these future lines will be much faster, because there will be fewer trees around.
However, there is a slight problem with this setting. In a regular binomial heap, trees are always kept in order. If we just keep throwing new trees in our collection of trees, combining them at arbitrary points in time and adding even more trees after that, there is no guarantee that the trees will be in any order. Therefore, we need a new algorithm for combining these trees.
The intuition behind this algorithm is as follows. Suppose we create a hash table that maps orders from trees to trees. Then we could perform the following operation for each tree in the data structure:
- See if there is still a tree of this order.
- If not, insert the current tree into the hash table.
- Otherwise:
- Merge the current tree with a tree of this order by removing the old tree from the hash table.
- Repeat this process recursively.
This operation ensures that when we finish, there will be no more than one tree of each order. It is also relatively effective. Suppose we start with T common trees and end with t total trees. The amount of the total merge that we finish will be T - t - 1, and each time we perform the merge, this will take O (1) time. Therefore, the execution time for this operation will be linear in the number of trees (each tree is visited at least once) plus the number of merges performed.
If the number of trees is small (say, & Theta; (log n)), then this operation will take O (log n) time. If the number of trees is large (say & Theta; (n)), then this operation will take & Theta; (n) but will leave the remaining trees only & Theta; (log n), which will make future detections much faster.
We can quantify how best this will be achieved by performing a depreciated analysis and using a potential function. Let & Phi; be our potential function and let & Phi; the number of trees in the data structure. This means that the transaction costs are as follows:
- Paste : Does O (1) work and increases potential by one. Amortized cost - O (1).
- Merge : Does O (1) work. The potential of one heap drops to 0, and the other potential of the heap increases by the corresponding value, so there is no net change in potential. Thus, the amortized cost is O (1).
- Dequeue-Min : Does O (#trees + #merges) work and reduces potential to & Theta; (log n), the number of trees that we would have in a binomial tree, if we are happy to collect the trees together. We can explain it differently. Let the number of trees be written as & Theta; (log n) + E, where E is the "excess" number of trees. In this case, the overall work is done & Theta; (log n + E + #merges). Please note that we will do one merge per extra tree, and therefore the general work is done & Theta; (log n + E). Because our potential reduces the number of trees from & Theta; (log n) + E to? Theta; (log n), the potential drop is -E. Therefore, the amortized cost of dequeue-min is equal to & Theta; (log n).
Another intuitive way to understand why the amortized cost of dequeue-min is & Theta; (log n) is to look at why we have redundant trees. These extra trees are there because these damned greedy inserts make all these extra trees and don't pay for them! Therefore, we can "recharge" the costs associated with performing all the mergers into separate inserts that took all this time, leaving behind the "core" & theta; (log n) "core" and a bunch of other operations that we will blame on the insets.
In this way:
Modification 3 . In dequeue-min mode, consolidate all trees to provide no more than one tree of each order.
At this point, we have an insert and merge in O (1) time, and the decomposition is performed in the depreciation mode O (log n). It is wonderful! However, we are still not working with downsizing. This will be a challenge.
Step Two: Implement a Reduction Key
Right now we have a “lazy binomial heap,” not a Fibonacci heap. The real change between the binomial heap and the Fibonacci heap is how we implement the reduction key.
Recall that a key reduction operation must accept an entry already on the heap (usually we have a pointer to it) and a new priority that is lower than the existing priority. Then it changes the priority of this item to a new, lower priority.
We can implement this operation very quickly (in time O (log n)) using a simple algorithm. Take the element whose key should be reduced (which can be located O (1) times, remember, we assume that we have a pointer to it) and lower its priority. Then change it repeatedly with the parent node until its priority is lower than its parent, stopping when the node stops or reaches the root of the tree. This operation takes O (log n) time, because each tree has a height of no more than O (log n), and each comparison takes O (1) time.
Remember that we are trying to do even better than this - we want the runtime to be O (1)! It is very difficult to connect. We cannot use any process that will move the node up or down the tree, as these trees have a height that can be & Omega; (log n). We will have to try something more decisive.
Suppose we want to reduce the node key. The only way that the heap property will be violated is with the new node priority lower than its parent. If we look at the subtree embedded in this particular node, it will still obey the heap property. So, here is a completely crazy idea: what if every time we reduce the node key, we cut out the link to the parent node and then bring all the subtree embedded in the node back to the top level tree?
Modification 4 : reduce the key of the node key and, if its priority is less than its parent priority, cut it and add it to the root list.
What will be the effect of this operation? A few things will happen.
- the node that our node previously had as a child now thinks that it has the wrong number of children. Recall that a binomial tree of order n is defined as having n children, but this is no longer the case.
- The collection of trees in the root list will grow, increasing the cost of future dequeue operations.
- The trees in our heap will not necessarily be binomial trees. They can be “previously” binomial trees that lost children at different points in time.
The number (1) is not a problem. If we cut a node out of our parent, we can simply reduce the order of that node by one to indicate that it has fewer children than previously thought. The number (2) is also not a problem. We can simply reload the additional work performed in the next dequeue-min operation using the reduce operation.
Number (3) is a very, very serious problem that we will need to solve. Here's the problem: the efficiency of the binomial heap partially stems from the fact that any collection of n nodes can be stored in a collection of trees & theta; (log n) of different order. The reason for this is that every binomial tree has 2 n nodes in it. If we can start cutting knots from trees, we run the risk of having trees that have a large number of children (that is, a high order), but which do not have many nodes in them. For example, suppose we start with a single tree of order k, and then perform key reduction operations for all grandchildren k. This leaves k as a tree with order k, but contains only k + 1 common nodes. If we repeat this process everywhere, we can get a bunch of trees of different orders in which they have very few children. Therefore, when we perform the coalece operation to group the trees together, we can not reduce the number of trees to the control level, breaking the & theta; (log n) -time, which we really do not want to lose.
At this moment we are a bit attached. We need to have more flexibility about how trees can be changed so that we can get O (1) time reduction functionality, but we cannot let the trees get changes arbitrarily or we end up with a decrease - the key amortized runtime increases to a value greater than O (log n).
The necessary insight - and, frankly, what I consider to be a true genius in the Fibonacci heap - is a compromise between them. The idea is this. If we cut a tree from its parent, we already plan to reduce the rank of the parent node by one. The problem really arises when a node loses a lot of children, and in this case its rank is significantly reduced if no node is higher in the tree, knowing about it. Therefore, we will say that each node is only allowed to lose one child. If a node loses a second child, we will shorten its node from its parent, which distributes information that the nodes are missing in the tree.
It turns out that this is a big compromise. This allows us to quickly reduce keys in most contexts (as long as the nodes are not children of the same tree), and only in rare cases do we have to “propagate” the reduction by cutting the node from its parent and then cutting this node from its grandparents .
To keep track of which nodes have lost children, we will assign a “mark” bit to each node. Each node will have a bit bit label, but whenever it loses a child, a bit will be set. If it loses the second child after the bit is already set, we will clear the bit, and then cut the node from its parent.
Modification 5 . Assign a label bit to each node that is initially in error. When a child is cut out of an unmarked parent, mark the parent. When the child is cut out of the marked parent, deselect the parent and cut the parent out of its parent.
To this older question , I sketched a proof showing that if trees are allowed to change in this path, then any tree of order n must contain at least & Theta; (? phis; n ) nodes, where? gold ratio , about 1.61. This means that the number of nodes in each tree is still exponentially in the order of the tree, although it is a lower value from the previous one. As a result, the analysis we did earlier about the time complexity of the key reduction operation is still preserved, although the term is hidden in the & Theta; (log n) will be different.
There is one last thing to consider - how about the complexity of the decrease key? This used to be O (1), because we simply shortened the tree embedded in the corresponding node and moved it to the root list. However, now we may have to perform a “cascading cut” in which we cut a node from its parent, then cut this node from its parent, etc. How it gives the keys to reduce time O (1)
The observation here is that we can add a “charge” to each key reduction operation, which we can then spend to cut the parent node out of its parent. Since we only cut the node out of our parent, if he has already lost two children, we can pretend that each key reduction operation pays for the work needed to cut out the parent element of the node. When we reduce the parent, we may charge for it, returning to one of the previous operations with the reduction of the key. Therefore, despite the fact that any single operation with a key reduction can take a lot of time, we can always amortize the work on earlier calls so that the execution time is amortized by O (1).
Step Three: Linked Lists Abound!
There is one final detail that we should talk about. The data structure that I have described so far is complex, but it does not look disastrously complex. Fibonacci heaps have a reputation for being scary ... why is this?
The reason is that for the implementation of all the operations described above, tree structures must be implemented in very smart ways.
As a rule, you represent a multi-level tree, either having each parent point for all children (possibly having an array of children), or using the left-child / right-sibling function , where the parent has a pointer to one child, which, in turn, indicates a list of other children. For a binomial heap, that’s fine. The main operation that we need to do on trees is the union operation, in which we make one root node a child of another, so it is quite reasonable for pointers in the tree directed from parents to children.
The problem with the Fibonacci heap is that this representation is inefficient when considering the step of decreasing the key. Fibonacci heaps should support all the basic manipulations of the standard binomial heap pointers and the ability to cut one child out of the parent.
Let's consider standard representations of multivariate trees. If we represent a tree, if each parent node stores an array or a list of pointers to its children, then we cannot efficiently (in O (1)) remove the child of the node from the list of children. In other words, at run time, the decrement key will dominate the accounting step to delete the child, rather than the logical step of moving the subtree to the root list! The same problem appears in the representation of "left-child", right-brotherhood.
The solution to this problem is to save the tree in a bizarre way. Each parent node stores a pointer to one (and arbitrary) one of its children. Then the children are stored in a circular list, and each indicates a parent. Since it is possible to combine two cyclically linked lists O (1) times and insert or delete one record from one O (1) times, this allows you to effectively support the necessary operations of the tree:
Make one tree a child of another: if there are no children in the first tree, set its child pointer to the second tree. Otherwise, splicing the second tree into a cyclically linked child list of the first tree.
Remove the child from the tree: connect this child to the node with the linked list of children for the parent node. If this is the only node selected to represent the children of the parent node, select one of the sister nodes to replace it (or set the pointer to zero if it is the last child.)
It is absurd to consider and verify many cases when performing all these operations simply because of the number of different cases of edges that may arise. The overhead associated with all pointer juggling is one of the reasons why Fibonacci heaps are in practice slower than their asymptotic complexity can offer (the other big one is the logic to eliminate the minimum value requiring an additional data structure).
Modification 6 . Use a custom tree view that supports efficient tree joining and cutting one tree from another.
Conclusion
I hope this answer sheds light on a mystery that is a bunch of Fibonacci. Hope you can see the logical progression from a simpler structure (binomial heap) to a more complex structure with a number of simple steps based on reasonable insight. It is unreasonable to want to make inserts amortization-efficient due to exceptions, and this is also not too crazy to implement key reduction by cutting subtrees. From there, the rest of the details are to ensure that the structure is still effective, but that is more the consequences of the other parts, not the reasons.
If you're interested in learning more about Fibonacci heaps, you can check out this two-step series of lecture slides. Part one introduces binomial heaps and shows how lazy binomial heaps work. Part Two explores Fibonacci heaps. These slides take up more mathematical depth than what I examined here.
Hope this helps!