Video 3-4: Fibonacci Heaps -- Informal Overview

0:02 In the next section, I want to introduce Fibonacci heaps. Um and also not really introduce them. That's why I called it informal. Uh I will sketch the main ideas, but not go through the analysis. I'll mention a few things about it in a second. Uh first of all, these lazy partition heaps have a good chance of being very good in practice if you need the prior the decrease key. Um in other words, the stable pointers. And maybe something Well, original binary heaps are rather good in practice to be honest. Um maybe the quick heaps are close to that. Uh can support a little bit of of the other operations. Um but let's let's take the whole uh completely theoretical lens on this. Then all we've seen so far is is not clearly optimal. There's no reason why we couldn't get all operations to constant time except maybe for one. Like delete min. Also melt we couldn't really do.

1:06 So ignoring any practical concerns for now, is there any way to do this? And the answer is a resounding yes. Uh there's actually many ways known by now. And I'll show you a different one in the in the next subsection, but uh the historically first was uh the Fibonacci heap.

1:26 And I think mostly for that reason it's still widely taught and widely mentioned. Um I don't think it's by any standard the easiest or convenient or most practically uh promising data structure. It just happened to be the first. Uh but that's still something. Uh so I thought instead of not mentioning it at all, I'm going to give you the key facts about what they are, but skip any of the proofs and analysis. If you want, uh you find full details in, for example, the Cormen book.

2:11 If I'm not mistaken, so Cormen et al. Introduction to Algorithms. Uh standard book for algorithms and data structures. If I'm not mistaken, the newest edition actually kicked out Fibonacci heaps because they also didn't teach it anymore. Which is kind of good news because they put these removed chapters for free on their website. >> [snorts] >> So, in a way, by kicking it out of the book, they made it more accessible. How funny, eh? Well, maybe that speaks to the point that there's um other things that they found more more valuable to have in the book. What is a Fibonacci heap though? I think for historic reasons, it's good to know roughly what it is, even if we don't dig through the details. First of all, a Fibonacci heap is really a a forest, a collection of several trees. And that gives us more flexibility. So, you should really think of it as, say, a linked list of nodes, each of which is the root of some tree.

3:20 And these trees can be essentially arbitrary shape. In particular, they can have more than two children. They're not binary trees. And they could, in principle, have chains of unary nodes. Um going to This is just a cartoon, okay? This is not supposed to represent any any actual snapshot of uh Fibonacci heaps. You'll see in a second why maybe this is indeed not possible. In principle, unbounded degree, but heap ordered. Okay, so that is the only thing that we keep. So, still the minimum of every subtree will be in the root. And the minimum of the entire data structure will be one of the roots. And the it's easy to keep a pointer to that minimum and keep that updated while you're uh doing operations on the data structure.

4:21 The children are also ordered. There's a first or leftmost child and a a second and so on so forth child, but there's no single left. So, if you have a single child, that's just your child. If you have several, there's an order from left to right. Which, if you draw it or represent it in a computer, is hard to do otherwise anyways, but that's um uh mathematically speaking is of course um a restriction as compared to say a general graph that doesn't happen that happens to not have cycles. That's also a tree. So, here we That's what we mean by ordinal trees. So, yeah.

5:03 Ordinal tree means these two things. Okay. Um that's that part. Heap ordered by priority queue by by priorities as in in heaps with as we've had it so far. Uh the trees are actually represented so that you don't need an unbounded number of child pointers. So, technically speaking, they're represented as this first child next sibling. Just think of it that the children have a a linked list among themselves. That's the first part why it's annoying to deal with those. And for the you can ignore this for the high-level overview. It's just a a way of a low-level representation that doesn't have a a variable number of pointers.

5:47 Next, um every node has a certain rank, which is some very uh mildly intuitive quantity. It happens to be only one of two possible values, namely either the rank is the degree, the number of children, or it's the number of children plus one. And if the rank of a node is one more than its number of children, that means it has lost a child at some point. Poor guy. And so, uh we treat such a node or we we we we call such a node marked. And this is stored in the nodes, so it's remembered whether or not the node is marked or not. Uh then there's this curious invariant. Um if you look at a a node in your tree, it may have a lot of children, right?

6:45 If you look from the right at the ith child, then the the rank of that child is supposed to be at least I minus one. I whatever, right? We may not care too much. These all have some subtrees. Uh effectively, what it means is that uh the further you go to the left, the larger the degree of these of these children has to be because the rank is at least the degree. So, that already shows you these trees need to get fairly big if they have large degree, then there need to be a lot of nodes below them. Because again, these also recursively satisfy the same invariant. I'm not I'm not claiming that this is highly uh intuitive, so.

7:39 Okay, that's the setup. Um with that, we can do operations. And indeed, I think the um the general setup of having a collection of heap-ordered ordinal trees of whatever sizes, and somehow um maintaining them so that you uh do operations in this way, that's shared among many data structures. So, maybe this is uh worth having a a a quick think about even outside of the scope of strictly Fibonacci heaps. Uh for find min, as I said, we maintain one pointer that tells us which of the roots is currently the smallest. And you'll you'll see that the other operations, you can always maintain this. Insert X adds a new element X as a single mini tree to the data structure. First point here, if X is smaller than the current min, min points now to X. Easy. If not, then min stays. Melt, if I want to union two two Fibonacci heaps, you just take the union of their collection of trees. Put them next to each other, nothing else.

8:51 The minimum now points to the smaller of the old minima. Also easy. Okay, so let's do Maybe with a some fewer. And then you update min to be the the smaller of the two min.

9:22 More interesting is delete min. So far, we've done nothing to ever reduce the number of of trees. Is there especially if I start from empty and do insert insert insert, I'm going to get this long chain of single elements. That's not going to apply. Uh delete min has to eventually do something. I'm finding the minimum with my pointer, then I remove that root. Now, that leaves all the children of that former element kind of as foster as as as a um orphans. So, I add them to the forest as new uh grown-up roots of a tree of their own. That might even further increase the number of trees, but now I'm applying a rule to get rid of some trees. Namely, I I check that afterwards I only have at most one tree of a given rank at the root. So, formally I bucket sort by rank, which means I I group the trees by the rank of the root.

10:22 And whenever I have two with equal rank roots, I call this link operation that I'll come to in a second. But once you're done with that, link always makes uh a larger tree, so the rank will go up. Eventually, you'll have at most one root for each rank, and that will bound the number of trees in the end. But you'll have to work your way through there. Uh what does link do? Link gets two trees, or their roots, rather, and just takes the smaller of the two as the root of the new tree and makes the other a new child of that other tree. So, this could look like this. Uh here's one. That's T1, that's T2. Uh say this is X, this is Y, and say X is smaller.

11:14 Then, I'm going to turn this into a single tree um where now Y and its entire subtree joins as a new tree here, and it's important that this this becomes the leftmost child of of uh X. And the reason is that we don't want to mess up the rank. Right? Uh remember this invariant here that uh the further I go left in the list left in the list of children, the larger the rank has to be. And here I'm I'm calling link always on two equal rank things. So uh I'm safe to put it here.

12:07 So far, that sounds fairly clean. You have uh simple operations for these cheap operations simple implementations for these cheap operations. At delete min, you have to eventually do the work of reducing the trees. Now, decrease key um the first part is also very natural. If you have within some large tree, you have your node X. Now, you you want to change its key to something smaller. That means it might violate all the path up to the root. And we don't have This is supposed to take constant time. So, we can't really do much walking up the tree and fixing things. The only thing we can do is take X and its subtree and just remove it from this entire thing. And make it join make it join the list of grown-up trees by itself. And then here it's gone. So, you you rip it out from the tree. That means you can now set X to whatever smaller value you want.

13:10 Uh that's only going to make Now, come on. Black, please. That's only going to make the heap property in this tree hold even stronger, if you like. But, the problem is that now here in here I created a hole. And the former parent of X might now violate its invariant. And if that happens, you have to recursively cut the parent. And this is the main cause of frustration in Fibonacci heaps. This is is further for one it's it's annoying to execute. You're escalating up the tree. It will amortize away to constant amortized time in the end. Uh but this makes both the implementation and the the analysis messy. But you can't simply have uh the rest of the invariants hold and ignore this step. So seems seems the only way to do it.

14:12 All right. Uh with that set up, here's the key steps for the analysis. And I'm not going to You're not going to understand why the rest follows. I mean this is uh in a way I'm I'm skipping the details. So one key lemma is that you can show the rank in a node of any node in an in a tree is bounded in terms of the total number of elements in this data structure and it's logarithmic. You can just in a simple inductive proof up to this point where you just show that uh whenever you have some node, it has at least two children of rank that node's rank minus three. That's generous. So you still have some sort of exponential growth in the trees. So they're somewhat balanced and hence have low height. Um if you want uh you can make this more precise and that's where the name comes from because the precise size bounds involve Fibonacci numbers.

15:09 And then for the ana- for the amortized analysis, you pick this magic potential which is two times the total number of marked nodes in the data structure. Remember these were those that had a rank that is bigger than its degree by one. Uh plus the number of roots to the number of trees in the in the oval data structure and you can show that with that potential uh everything goes through, but um in particular the analysis of decreased key is rather messy. So, I'm not going to do it. If you want to look it up, um be my guest. I consider this relatively uh complicated for what we get. Uh you'll see we have another option that I think is is much cleaner. But at least now you have a a quick a rough idea of what Fibonacci heaps do. Uh the key steps again is a forest of heap ordered trees. The trees have arbitrary degree almost. It's not completely unbounded, but not just binary.

16:12 And the key operations are relatively simple if you're in this model. Insert, well, add a new tree. Find min, it's going to be one of the roots. Meld, just concatenate all the trees. All the complication is in delete min and maybe in in decrease key. In an ideal world, decrease key would be only the first step. Rip this guy out of its tree and make it a new subtree and stop there. That would be nice. Fibonacci heaps can't.