Video 3-5: Quake Heaps Overview

0:03 The final data structure in this unit that I want to present are quake heaps. And uh the name comes from an operation that that simulates an earthquake, very dramatic, a seismic event that restructures the the the tree a lot. You'll you'll see um tomorrow what this looks like. Uh again, the goal is still the same. We'd like a theoretically optimal priority queue, but maybe without some of the complications that Fibonacci heaps had to uh suffer from.

0:39 Um the focus here even more is ruthlessly on the theoretical running time and we're not going to care at all about how to implement this. Uh, I should say it's it's there's nothing stopping it from being okay in an implementation, but it's not going to be the focus.

1:11 There's one thing I want to point out at this point which uh I also found found a bit confusing. We may um we may actually come back to this uh in the next chapter in a bit more detail. Uh details of the model of computation matter at the question what the precise running time is. Uh and in one subtle thing that Fibonacci heaps used was upon the deleteman they did this bucket sort of all the trees by their rank and that's fine. The ranks are small integers. So sorting there means you allocate an array with positions for all the ranks that can occur and then you just in a way hash an a tree to the position indicated by its rank. That allows you to sort in linear time which only works because you're sorting small integers. More on what you can do with integers in general um next week the week after. Uh this is okay in a way. We can do this on our word RAM machines.

2:19 But you'll see next next unit that this this uh use of arrays implicitly in this bucket sort is a potential further restriction or a downside of Fibonacci heaps. Um this is in a way shared by what's to come. Um, we're also going to use this and I think it's uh to some degree open if you can even get constant time decrease key if you don't allow this uh at least um is is way harder to to achieve. Okay, that's that's a nitpick. Um for now let's uh ignore that uh and look at the overall structure of this new data structure quake heaps. Uh at the highest level quake heaps are again a collection of trees say like Fibonacci heaps but we keep each of them as a tournament tree that will turn out to be more convenient. Uh that means remember all the data is only in the leaves and every internal node is just a copy of something that's in the leaf.

3:29 Now here we're going to be less restrictive with the shape. We're not going to have this perfectly uh almost complete binary tree, but instead um every note can be binary or unary. If it's unary, because it's always going to have uh one child with the same key. If it's unary, it's going to have only that child. Right? So, these are rather useless or boring nodes, but you'll see they make make the overall uh structure easier. And we don't have a fixed um no no constraint on the shape of these trees at all other than being binary or unary. So what what you should think of this what this looks like we have collection of these trees. They're all binary.

4:19 Maybe there's some smaller some larger ones. Um otherwise an unrestricted collection of trees. and what each of these looks like. Um, almost a example from before, but now with this weaker constraint of the shape. Um, let me try to draw a somewhat general example.

4:51 Again, these these values are not at all in any specific order. That's just how they came. I'm also going to assume that these are represented as pointered structures. So each of each of the nodes that I'm drawing here is an object and um let's see each of the nodes is an object and it has pointers to uh various things. I'll I'll comment on that more um tomorrow.

5:32 I'm going to rearrange this so the drawing is so that the equal keys are on top of each other where possible. That's not going to be enough. One more level.

6:15 And you see from uh if you try to construct this example, you always have a lot of choice uh which two to combine. You can choose uh various options um because you can decide to just keep a thing single for this level like I did with the four here. It's kind of an extraneous note. But you can can do this here if you want. So here maybe we decide the three stays here. The one unites these two and then the one here unites the whole tree.

6:51 Uh so in particular there's unary nodes, right? They can be at any height. has one equal value child And that's what these nodes are going to store as well. Uh on top of that, we have levels in this tree starting with zero at the bottom. So uh they're all numbered up from zero. And uh here at level zero, we have these nodes.

7:57 uh n0 this will will pop up later again um probably have to give you the notation tomorrow again anyways so this is one of these trees overall you'll have a collection of those and so far um completely unrestricted uh it'll make the description a bit easier to have these as tournament trees as opposed to these uh unbounded degree things. Um but because they're so unrestricted, you maybe can already imagine that many of the operations will be simple and similar to Fibonacci heaps. For example, an insert can just add another tree or um a decrease key can essentially rip out a sub tree and make it a new single tree of its own. Melt can just take the union of these two collections of tree of lists. But eventually at some point we'll have to get rid of these many many many trees to get the running time bounded. So the interesting part will be delete min again.