Video 3-6: Quake Heaps Operations

0:03 Let me briefly recap what we discussed about quake heaps yesterday. Uh first of all, still the goal is to have a theoretically optimal priority queue. I'm slightly emphasizing theoretically because I think not much else can be claimed from recover. Uh they'll share this subtle assumption with Fibonacci heaps that we use arrays for precisely the same kind of trick. we'll want to bucket sort uh trees in some specific way. You'll you'll see uh um let's focus on on the structure again so that this is fresh in everyone's mind. Um unlike Fibonacci heaps the the trees that a quake heap consists of are tournament trees. This is more of a cosmetic thing. It just makes the definition cleaner. Um let me maybe point out if you follow here if you take the root and follow its path of equal value children you could also turn this into one uh horizontal node at the top and attach all the children that hang off from this as the children at the root and you can recursively do the same. So in a way um there's a bjection between these tournament trees and an ordinal tree where the degree is unbounded but you don't repeat the keys.

1:28 They are not so far apart from each other in terms of how they behave as data structures as this may may uh hint at. Um what we'll use these tournament trees here for is specifically these levels and that is kind of more convenient to describe in tournament trees. That's the whole reason why quake he keeps use tournament trees. They could otherwise be reformulated but the the whole rules as you'll see will be would be less natural. So tournament trees again tournament trees have all the keys in the leaves and they are binary trees but we relaxment trees here to also allow unary nodes in between. So in in principle, these could be arbitrarily tall because you could have towers of unary nodes that go up as much as you want. So this will we'll have to get rid of um as you'll see. But for now, unary nodes are in principle allowed. Um every internal node stores um it's it always has each of these has an equal value child might be one of the leaves if it's at le level one and it may have one other child or it may not that's optional.

2:55 we also store for each of these nodes uh what levels they are on. So every nodes here remembers its level that it is. Um I don't think it needs the parent but it stores a pointer to its leaf down here. So you can jump in constant time from the root say down to this leaf one and its leaf. Uh I'm making this sound as if it is clear that there's only one. There is only one because this is the single leaf that has the same value or same priority as this note. You know there always is one because you can always follow the equal value child link, right? That's what uh the tournament trees give us.

3:50 Um uh we also need the the total height uh is just the largest level where there's any note on. So this tournament tree has height four.

4:22 I think I need a bit space maybe just in in preparation. Uh I I said a to a quake heap consists of a collection of such tournament trees. Uh what we precisely store in a quake heap to make the operations work um is is slightly uh slightly more general than this. Um, but we'll split them by height or we keep them by height so that we can access all nodes on a on a specific level efficiently. ly.

5:30 Okay, we'll come come back to that. I think it's time for a little bit of uh notation to talk about these more more ser more sensibly. Uh the levels I introduced in my example tournament tree. Maybe we can borrow this one. Of course, the overall quake he will consist of several of these.

5:54 I could have just selected and then I can doesn't need to be a rectangle. Oh, no. I want this part of it. Okay. Early morning.

6:13 So, I have the the levels in a single tree. Um the largest is always going to be h the height. Um now we in general have several of these trees. Uh let's add another one.

6:38 but just deleting some things. Um maybe also make it less tall. What we'll also denote what we'll also need is the number of nodes on a certain level. That's these n little ns and they are u meant summing over all the tournament trees. So uh we have n0 here that's the leaves which that will always be the number of keys currently stored in the priority queue. And then you'll have a certain number of nodes on the higher levels. All of these will be promoted keys. So it can't be more than I had on the lower level. It could remain essentially the same if all of these are unary nodes. So I have n1 nodes in total on this layer one. Uh let's cheat a bit.

7:37 And and so on up to nh. Okay. And we'll also need the total number of nodes in the entire data structure. This capital n is just the sum of all levels. Okay. Um and here height uh is also meant uh of course every tournament tree has a height but uh by age I want to denote the height of the entire quake heap which is the height of the tallest tree. And what we'll need in the analysis in a second is the number of unary nodes on the level. So we have n i for total number of nodes on level i and ui for the unary nodes. Uh there's none in the lowest level. So this is always going to be zero u0. Uh but for all the other levels we don't know how many there are. And again the total number of unary nodes uh we'll also uh need in the analysis. And the last parameter is the number of trees that's capital t.

8:35 So we have three key quantities that dis describe the the size of a quake heap. The number of um total nodes then how many of those are kind of useless because they don't reduce uh the tree shape and the overall number of trees.

8:58 Um, quick heaps have one strict invariance, which is this, that on any level above the lowest leaf level, I should essentially lose a constant fraction of material. So whenever I go a level up, I'm losing at least a third of the nodes. In other words, I can have a mix of binary and unary nodes, but can but I cannot have only unary nodes.

9:27 More precisely, I guess what this means is that I have half binary half unary in the worst case, right? Then uh if if I have a certain number of nodes here and I want only 2/3 of that number one level up, I can pair up some. And then what's the 2/3 of eight doesn't work so well. Maybe let's make it nine. Then it's it's precisely six, right? So I can have six notes up here, for example, like this. And then you see I have exactly half binary half unary. That's the worst case that we allow. And this is supposed to be a strict invariant true at every level. So on every level I can have at most half of the nodes be unary, right?

10:41 Now we'll see um this this keep this invariant in in your in mind for now. Um this will occasionally be be violated and then we have to do something about it. We'll only come back to this um a tiny bit later. But if that invariant is guaranteed clearly we can say something about the height of the tree because uh this is geometric geometrically decreasing. If I start with a certain number of elements um I think confusingly little n is the number of keys.

11:20 Maybe I should have said n0 which is what I mean here. Um, same thing. I think uh it's convenient to to use n for the size of the data structure. Uh, but there's a three different types of ns flying around. Okay, there's little n number of keys, same as n0. There's the n i on the other levels and there's the capital n. So, I have to be um careful with what I'm pronouncing these like. Uh because because we use it lose a constant fraction each level we go up. you can easily show that at each level you're uh inductively 2/3 to the level n that's the fraction you lose across these levels. So um by generously rounding this is roughly uh well one over square <unk>2 if you like it's just more convenient to calculate instead of keeping the 2/3 I prefer powers of two that's all. Okay. Now if you take this equation and solve for when is this quantity our ni when is this less than one? Well once i becomes larger than 2 login n. Okay.

12:31 So this height bound just comes from this geometric decreasing. I lose a constant fraction. So after logarithmically many steps I'm down to a single node in the worst case. And this is I think you cannot even achieve this height. It's this generous upper bound. But the two login is easier to work with and sufficient for what we want.

12:57 So far so good. Now next we should look at operations. Uh how can quake heaps support the typical operations on uh on heaps that we have.

13:15 And the first one is insert. What would you guess? Uh, from what I told you, all the operations should do very little work except for deletement.

13:36 It's certainly a tournament tree at some point. So, I have to add this new leaf. And then what else? Nothing else. Let's just take this as a a tiny tournament tree.

14:07 So you um add a new tree to your collection. Uh the root of this one is just the note the leaf itself at level zero and that's it. Constant time, right? Uh that was the easiest. Let's look at decrease key.

14:29 Uh you know what? Melt is even easier. I think Mel is given these two priority cues, Q1 and Q2, both of which are quake heaps. From what I told you before, I guess uh you can you can guess what we do.

15:11 both of these are quake heaps. So they consist of a list of such tournament trees and they're in both cases already ordered by the level but I can just concatenate all the lists across the levels. What I mean um with this representation a while ago [snorts] what the quake heaps store is the the notes by level but if both of them do that I can concatenate all the lists on each level. Uh I I'll have to do that somewhat lazily right otherwise it's not constant time.

15:54 I think we can probably do the split by level also lazily we'll only see it when we talk about the delete min operation really. Uh one thing we should also keep in mind is we have an invariant that we have to keep keep valid and the invariant said something about the notes on levels. So if I add a new leaf that doesn't add any nodes to higher levels. So it might make it easier to satisfy the invariant for level one and it doesn't make it any harder for any levels further up. So that's never going to touch the invariant. And for this for the melt operation, the two quake heaps I'm starting with satisfy the invariant. So also their combination will satisfy the invariant. We're just adding up the levels and they stay stay the same on each level.

17:15 So how about decrease key um of say some pointer to a new value x prime here the assumption again the assumption is I have some some handle into the data structure that directly tells me uh say this this is the leaf I'm I'm trying to change.

17:46 Uh, one more thing in the structure that I think I didn't mention. We talked about the internal nodes. The internal nodes store these things. The leaves also store something.

18:22 Maybe I can color code these things a little. So there's uh there's a pointer from every leaf to the highest note that stores that same value and so forth. Uh whereas also these internal nodes have a pointer down. So uh it's going to get messy if I try them draw them all. They would all point down here. Uh what this means for decrease key is if you're given a leaf node that's where the pointer goes to you can follow this orange pointer to the highest internal node that stores the same same key same value.

19:45 And so then we're in this situation. Uh there's some larger tournament tree. There's our leaf here which we now want to change. Currently this is X.

20:12 with further things hanging down and our orange pointer goes from X up here. Now I'm going to just take this one note further. Uh by definition, let me make this a bit bigger.

20:30 this this is going to have some parent unless it's the root already in which case we're um it's maybe a one point uh it's the easiest case if if this is already the root of the entire tournament tree I can simply change the value of x to something smaller and update these these nodes and And um again we won't store a copy of X in these notes really. We store a pointer to the leaf so that we can update the value in the leaf. And all these pointers if they ever need to look up their value they look into the leaf. So you can change it in one place.

21:26 The reason why here the update is easy is because I cannot disrupt the heap order. The heap order will was satisfied before and if I make the value of the root smaller uh this remains the minimum. That's the easy case. Uh in the other case that's what I'm drawing here. There has to be some other node which is smaller than x where x is the child of this node. Now clearly this node will have another child namely Y. So maybe again uh let's leave a bit more space so I can skip stay with my drawing style from before. This will go down until some leave Y and this is smaller. This means it's okay to rip X out of Y's uh parenthood.

22:20 Um, so we'll add this as a new tournament tree and remove this here. Gone. And y is still in a good shape. It still has one child. So it's not violating the the heap or the the structure properties. And once this is a tree of its own, I can again update x to x prime without violating the property. That's the same as um in the first case.

23:25 uh with that we can also do this this operation in constant time. Let me let me use uh the blue color for the actual cost. Can already annotate this while we're discussing the operations. I think um adding a single leaf here that's clearly constant time for melt. Uh we'll have to think about whether we can lazily do the the operations on the level lists or if we can delay that properly. Um if it's just concatenating the overall list that that works. This needs checking.

24:02 Um decrease key the way it's described here only follows a handful of pointers and um maybe changes the pointers here. All of this is also constant time using this trick that internal nodes don't have a copy of their value but point down.

24:35 now the most interesting operation is missing. We'll need to do our delete minimum. And at this point, some you have to expect something more interesting because eventually so far we've only created lazily created mess. we've added lots of trees. So there has to be some mechanism to bring the number of trees down. And as you'll see that mechanism is fine but that is the mechanism that might disrupt uh the invariant.

25:17 Um let's also think about the invariant briefly for decrease key. I'm I'm changing here the parent child relationship. But note that in terms of the invariant is strictly about the number of nodes on a certain level. And here I'm not changing how many nodes are on a given level. Level is counted from the leaves upwards. So this white tree where where this tree was before is at the same levels as it is afterwards. And I haven't actually touched any nodes. I haven't added or removed nodes. So also here the invariant is fine. Um I don't know maybe we should have a color for the invariant and uh kind of just write down that we've checked this. Uh I know this is not useful that much but um the uh the claim is that in each case it's easy to see that the invariant is not violated. Uh this will be different for deleteman. Leadman has several steps.

26:29 The first one, of course, we have to find the route with the smallest priority in the list of um of tournament trees. I think at this point, let me let me question this here. I don't think we need this um linked list of roots. Not not this. So just the uh list of roots of the tournament tree. Um this splitting by height is something you need in an operation but we only do it locally and and lazily.

27:18 I'll tell you later where I got this from. Okay. Um first step is find the root with smallest priority. Uh since we haven't spent any thought on how to do this fast, we haven't prepared for anything. There's a link list. So I need to to scan all the trees that I have. The actual cost for this will be linear in the number of trees. Capital T was the number of trees. Um maybe in in preparation here, let me copy this so that you have the Yeah, why not? Let's keep the invariant with it so that you can remind yourself of all the notation. Try to make it small and in the corner.

28:16 That's easy. Now, delete min is supposed to remove that element. So clearly we want to remove say that smallest priority is called X. We want to remove this. But what does that look like? X is a leaf in some tournament tree and it may have copies on various levels and these may have other children, right? There may be um one whole tree here. Maybe this is a unary node. It doesn't have a child, but it may have another one here and another one here.

29:05 So all of these sub trees that are hanging off here, I have to put them somewhere. So we're getting rid of rid of the entire chain here.

29:39 And that means I have to add these red trees as new trees into my data structure. Yet more trees. Yay. Joy, right? to the quake he keep. Uh what's the cost of this? Well, uh I have to delete all these nodes. I have to touch at least the height of this tree and I may also have as many trees to add to uh the overall list of trees. So this is the height of the tournament tree where X is located. In the worst case that's the height of the entire data structure. So the actual cost for this is H. And remember from our invariant tada this is logarithmic.

30:41 Uh this was consequence from the invariant uh the lema here or the corery here. So far so good. Um, but we've added yet more trees. So, we're not done.

30:57 We have a third step which eventually gets rid of trees. And, uh, let's call this consolidate. Conceptually what we do is while there are two equal height trees, And what does join mean? It's the only sensible option. You have two tournament trees that will have some root and you know they're of equal height indeed look like this. Uh one of the two keys will be smaller say X. So X becomes the root of the level one above and you add this as the other child. Right? It's the only sensible way how you could really deal with these tournament trees. Now, uh, at this point to make this efficient, now I need the trees sorted by height. Um, but I've already spent time linear in the number of trees. So, I can go through all my trees at this point. So, in a way, before I get to this loop, I can now bucket sort my trees by height.

32:43 And when I say trees, really it's the roots. Remember the quake heap is a list of roots of trees not stored by height. That was a mistake. Um just the list of roots, but the roots store their level. And so I can do this bucket sorting in linear time in the number of trees because the heights are actually small. uh small numbers. So I only need an array of size login. This is it's fairly moderate. Um if you wanted uh you could even try to do this with a binary search tree. Then you would need uh lo login time for each uh t * log login may also be tolerable. But here um for optimal times we uh we need to rely on bucket sort.

33:33 So that's fine. We finally have an operation that gets rid of trees because here I make out of two trees I make one tree. Uh what's a bit less obvious is how many trees this will leave, right? I mean um I'm just saying here you uh cook until done. You apply this rule as long as you can. But well once the rule is no longer applicable, I can have at most one tree per height. Right? If there were two equal height trees, I would have joined them. So the trees get taller over time, but I only stop once I run out of trees of equal height. Hence, afterwards, I will have only trees Okay. Um, we'll we'll use that later. Now, the key problem is that these these trees have become taller. And so, at this point, our invariant is really not clear whether this is satisfied. Right now, I've I've massively added new nodes and high up nodes. So, who can guarantee that this is uh is satisfied?

34:55 now and indeed it may not be or I guess yeah let's check the invariant for that you um you need to determine the number of nodes on each level Um, I think we'll do this top down to get the timing right.

35:53 That's a subtlety I uh I think we maintain we maintain uh no no we maintain the sizes but then again melt doesn't work. Okay that's a subtlety um that um is not clear to me if this is um is this covered. So how do I check the invariance? I need to know how many notes I have on each of the levels.

36:25 Um, I could have stored that, but then the melt operation needs to update it for all the heights. That makes it log in. We don't want that. Um, or I have to somehow recomputee the number of nodes on each level. uh but that is linear in the number of nodes overall potentially and we don't have time for that. Uh we want this we want to check the invariant and we want to pick the lowest level if there is one where the invariant is violated.

37:15 So where ni is strictly larger than 2/3 the level below and at this point an earthquake happens. Let me try try to to draw that first. Um At this point, they're such that there's only one tree of each height, but we could maybe not have some heights.

37:53 And so all all of these have their levels, right? There's lowest level and then one level above another so on. This of course is is just a a cartoon if you like.

38:17 And say there's um on a certain level here there's too many nodes too many unary nodes that really means. So on this level things are wrong.

38:44 Yep. And then what the earthquake does is it eliminates all the nodes higher than this level. So anything in this range above gets destroyed.

39:03 So maybe an earthquake is a bit of a a weird metapher for that. Uh maybe it's rather like a a chainsaw or so you cut all the trees to a certain height. Um and whoever stands stands too tall uh gets reduced. Now that of course means each each of the nodes on this um lowest bad level will now become the root of a tree.

40:06 uh and it's including the level I. So my drawing is a bit imprecise. I left the notes here. Maybe I fixed this by adjusting the drawing rather.

40:16 Uh, let me let me move the the red part a bit up. This is still good. The one above is bad. Oh, should have redrawn it. All right. So, there's there's a bad level where there's too many nodes, and that level is bad. So, we don't want to keep it. We take the trees on the level below.

40:49 Okay. So clearly this is an expensive event because it uh it clearly has to touch all this top part. So all this part of the trees with nodes high up. How many nodes are there? What's the actual cost of this? Um, I'll call this n greater or equal i, where this is just the sum of the levels above i because in general we don't really know how many these will be but it could be a sizable fraction of the overall quake heap. could be linear in overall number of nodes.

42:15 So there's this this puzzle left. Um I think this this we kind of resolved. Um melt can't really do the list of of roots doesn't need to be split. Um and uh so we still need to show that this overall has good costs. I mean what we've done so far is analyze the actual cost and that looks far away from tolerable.

42:43 If you sum up what delete min costs um that's what I wanted to do somehow get all of this on one slide. Again in blue for the actual cost what we have is T. We need to scan the root list. Um then login for destroying this one tree.

43:16 Um we have the the bucket sword part. That's another plus T. and that's the overall cost. Uh we're fine with the login part. We're not fine with either of the others. Number of trees could be linear. Number of nodes high up could be linear. So uh occasionally this operation is very expensive.