Video 3-7: Quake Heaps Analysis

0:06 So we've seen um that we have constant time for insert and decrease key and potentially logarithmic time for melt uh even in the worst case but delete min in the worst case takes linear time. So we need an amortized analysis to get to something more sensible. And we'll show that essentially these worst case costs remain but we can get the delete min amortized to logarithmic time. And before we h get there there's a small technical lema that I think is is cleaner to do first. So let's go there. Uh the potential function that we'll use um is this. I think I still have this uh little notation list here. The potential will be the total number of nodes plus a term for the total number of trees plus a term for the total number of unary nodes and uh the factors in front are chosen so that what we gain in one can pay for other things. That's why you need to choose certain multiples.

1:20 And so it it it maybe even it's intuitively clear that these unary nodes are kind of bad. We need we need to avoid having too many of those. And and so um there's a a little lema that we use that bounds the number of nodes if um we have a quake operation or I should say the other way around. Um, if the invariant the quake heap invariant is violated, that was the invariant.

2:05 Then uh what we remove in this quake operation is indeed a lot of unary nodes. and so in that sense uh quake does a good job because these unary nodes are useless from a data structure perspective and are just driving up cost. So let's first prove this this technical lema even if it's u maybe not so motivated um without doing the rest and then you'll see how it uh helps us in getting from um the potential to our amortized cost.

2:53 So first lema 33 I think again I want my little cheat sheet of notation. The first observation is on any level the number of nodes that I have there unless I'm so um This assumption cannot be violated for i= 0 because I'm using i= 1 greater i minus one. Clearly here i is at least one. So on level i, not at the leaf level, what kind of nodes can I have? Well, either there are binary nodes or there are unary nodes.

3:52 There's no other option. um on the level below this could be the leaf level. So um in principle there it could also be other things. Um but instead I'm I'm expressing this level below as where do where do these nodes uh end up on the level above? So if I'm at this level I minus one. Uh oh on the level below and on level I minus one I will have a certain number of nodes. Now some of these are promoted further up.

4:39 Some of them are not at all promoted and some are promoted with the parent being binary and some are with the parents being unary.

4:51 If that is I minus one and now I'm looking at level I one option is that I have a binary node here. Another option is I have a unary node. Another option is I have nothing. These could also be roots of some sub trees that are not present anywhere higher up. That's the only options. So on level I, if I have a binary note, that must correspond to two nodes on the level below. If I have a unary node, it corresponds to a single note on the level below. And what is left must be roots on level i minus one. And I think uh we don't have this notation yet for roots. So let me add it here to the list.

5:42 Well, this just means they have no parent. So these these two are obvious observations about these number of nodes just from definition. Now uh by assumption we have here that ni is large. the invariant is violated.

6:15 I'm using this first to rewrite n I as the sum of the binary and unary nodes. And I'm using this the second equation. Let's give this a name. We'll use it more than once.

6:28 Uh to rewrite this. So I have this annoying factor 2/3 in front. So I'll have 4/3 b I 2/3 ui and 2/3 r i minus one away here. Good.

6:52 Now I can bring essentially the use to the other side. and I guess also the bi. So I'm I'm comparing this side and this totally on the right. If I subtract 2/3 UI, I'm left here with uh one/3 UI and the bi is gone. So I have this greater sign. And what's left here? I'm subtracting 1 BI from 4/3 BI. That's 1/3 BI.

7:33 I subtracted the 2/3 UI. That's gone. These still are here. Now I'm using again on this bi my star equation from above. If I solve for bi here, uh you bring these to the other side and divide by two. So we have a half n i - one - a half r i minus one right so if you insert that you get this minus one these we can combine the ui are left sorry three halves r i minus one. Now this term uh is always going to be some non- negative number. So uh I can just drop it.

9:13 And so I'm almost done. I bring the UI half UI to the other side and divide by three halves. Right. That's what we wanted to to show. So if I have a quake operation at level I compared to the level below, I had a lot of unary nodes on my current level. It's kind of maybe it's even an obvious thing from what I said earlier. The invariant says I have at most half of the unary nodes. And here uh we're cleverly deriving that the unary nodes is more than a third of what's below. That's precisely the same. Okay, maybe overly uh formalistic to derive it that way. Let's look at the operations and their amortized costs next.

10:28 the actual costs we've already derived for insert and decrease key. These were both constant. For melt, well, I guess we have to live with the logarithmic cost. And for um delete min, we had number of trees, login, and potentially the quake cost.

11:08 But let's um let's let's se let's separate this out because we don't always have an earthquake. So let's say we have another operation quake.

11:30 And the quake operation itself if it happens has this cost n greater equal i where i again is from context. It has to be the index where we have the earthquake happening. That was the actual cost.

11:50 Now we have to analyze the change in potential. And again for each of the operations we have to check insert remember what the potential was that's the sum of these guys I can write this um not so much effort uh if the pen works it's the number of nodes two times the number of trees and six times the number of unary nodes total. What do we do upon insert? Well, we add another node. So, n goes up by one and we add another tree. So, t goes up by one.

12:45 Multiply that with a factor two. We don't change the number of unary nodes. So potential change is three. That's still overall constant amortized cost.

13:07 Let's let's again do melt first because it's really easy here. What does melt do? uh compared to the I mean then I have to define the potential like display trees over all the trees that we work with over the families that exist I'm not adding any nodes I'm not adding any trees I'm not adding any unary nodes if I look at the two separate quapes before and then the combined one after so here really the potential is unchanged how about decrease key I remember what I do um I find this one element and take its tree out.

13:54 So I'm changing things a bit. Now here I only get an upper bound if I'm in the lucky case that it's already um a tree of its own. The element I'm changing is the root. I'm not adding any nodes or moving any trees around. So I'm I'm not actually changing the potential. In the other case where I have to take the tree make it a new tree. I'm not adding or changing nodes but I add another tree and I create a unary node. My parent was a binary node before and now uh I turn it into a unary node.

14:32 Of course this is still constant uh but slightly more expensive if you like. So I think it's with the numbers is self-explanatory where they come from maybe not not uh write this down in detail.

14:55 Now for deleteman we have to analyze these different steps. Um, recall the steps were these. Maybe it's good to have them in small on the side. I don't know.

15:15 Clearly, the first step doesn't do anything. It's not changing the tree structure. It's just looking So for 0.1 the change in potential is going to be zero.

15:39 I'm not doing anything. Now for the second this is a bit more interesting. Um I have my my tree that I now destroy and I potentially have these trees hanging down.

15:59 So by deleting these nodes I free up one potential each right these are a minus one because n becomes one smaller by deleting that node. Uh then these trees I add.

16:18 So for each of these I get a plus two because I'm creating new new trees. I'm not changing the number of unary nodes. Um potentially I do I may take away some unary nodes if some nodes on this spine are unary. Uh that is kind of in the upper bound uh lost. All I can say as an upper bound is that in the worst case every node here generated a new tree. So my potential goes up by as much as this this total. So it's always a plus one for each uh tree that I have. I lose one but it doesn't compensate. So the overall potential goes up by logarithmic not by by uh I guess by h + one if you want to be precise and we know the height is logarithmic. Okay so so far um not too much has happened. The third part is this consolidate step. Um let's first look locally what happens when you join two trees.

17:45 So we have some tree of a certain height and we have this other tree of the same height. And now we turn this into say X and then these sub trees.

18:03 We clearly add a new node that costs us one, but we remove a tree because y is no longer a single tree. So this frees up one potential uh for for every operation for every join operation that we do.

18:34 So I mean let's first state the obvious. The number of unary nodes doesn't change. Um the overall number of nodes is compensated by what the trees release. Uh so I don't have to to count this extra note. It's paid for by the tree that's gone.

19:08 And what I have to consider is the difference between the number of trees I have after this operation and the number of trees I had before the operation. And the the thing is that the trees that I have after the operation is bounded by one tree per height.

19:35 And the height of the data structure can never be more than two login. I guess that's if the invariant is satisfied. It might be violated at this point, but it was satisfied before we started.

19:50 Uh so let me just say login here. The invariant was satisfied before we started. Now by joining these trees, I may generate more levels. Um but I can't generate more than uh than I've I have resulting trees. Uh so you're only adding login extra levels in this because this is a it's a binary tree. Even if you started with n things, you only need login levels to merge them into a single tree. So you have that many trees afterwards and the trees before we can just subtract.

20:41 And so this step pays for the consolidation cost. We have a cost of t. We're going through all the the the trees that we potentially have to join now. And this is released in potential via this operation because the tree has a cost of two and it pays for this for this node uh and for the cost to to deal with it and and join it.

21:22 I'll try to speed up then we can finish the analysis. Uh what's left is the quake step. Remember so far um uh the quake step had this cost suppose it happens at level I.

21:45 So the actual cost was this number of nodes on levels higher than that. The number of nodes clearly drops a lot because I delete all these nodes that are higher up.

21:58 That's precisely the potential we need to pay the actual cost. Now unfortunately that's uh that's not all that we have. The other parts of the potential may also change.

22:17 the number of trees um may increase, right? Because I'm I'm uh taking combining nodes away, but it's never going to be more afterwards. The number of extra trees I get is not more than the number of nodes on this level that I leave, which is this level n minus one. These are in the worst case all new roots if there weren't any before. That's the most I can add as terms of as as as new uh trees.

22:48 Now the number of unary nodes um can change in in unpredictable ways but clearly on these on the level I that I get rid of I'm deleting all those unary nodes. So I may delete many more higher up. I'm not touching anything lower down and I'm not creating any unary nodes. So I clearly use lose all those unary nodes on that level. And that is uh by the lema from before whatever the number was 33 I can bound that in terms of the number of nodes on this level. So in some our change in the potential can eat up the cost of the quake operation and now I have 2 * delta t right and now you see how the factors in the potential were chosen so that this exactly cancels because we can't really bound what this ni minus one is but we definitely need this potential to exactly pay for quake that's precisely the cost so the total amortized cost is the sum of the change in potential and the real cost for deletement and you see that the T and the N greater equal I is released in potential in these two places whereas we're left with a login contribution in both cases login actual cost are left and we get an additional contribution of the new trees of login.

25:17 Um one small remark at the end is the space usage is also bounded. Um basically we have that this total number of nodes is linear. um that follows from the invariant I guess uh directly is a geometric sum and so in particular also the unary nodes um this is true uh the number of unary nodes is bounded whenever you uh just satisfy after after uh the quake condition is is satisfied then this is true and you can check that the other operations don't destroy it. If you do an insert you're adding an extra element but you're never adding unary nodes. Um melt cannot create new unary nodes that weren't there before. uh decrease key adds a unary note, but it it only does so out of a binary note that you had before. And so um you're not you're not going to get more unary nodes than you had binary nodes at some point. So initially uh the number of binary nodes is bounded as always in a binary tree. they may decay to unry notes but only uh by making uh the trees smaller overall. So you're uh you're staying bounded in terms of the size with that. Um let's conclude this this uh this unit.

27:13 um except for melt which um I'm not sure if constant time is possible in quake he keeps uh quake heaps support all the operations uh fairly fast and logarithmic time for mel is still much much better than what any uh heap or so can do and clearly it can do insert and decrease key in constant time even worst case um I I think is among among the options a simple data structure. Now the analysis is is tricky in the details getting all parts to work out um but still relatively clean and in a way um the best possible priority queue.

28:06 Uh this this mel thing bucks me but maybe there's a solution for that too. uh the tournament tree representation uses lots of extra pointers which clearly hits hurts a bit if you implement it in a in a straightforward way. Uh so again it's mostly a theoretical data structure but you've now seen an essentially optimal priority queue at least in theoretical realms.