Video 3-4: Operations on Binary Heaps

0:03 Let's next look at a few operations unless there are questions just stretching. >> we'll come to that I'll I'll tell you in a sec. This is precisely the the next part. Um we'll look at all the operations briefly in a row and then uh you'll see where the benefit of the structure comes in. In the next section we'll look at the operations on the binary heaps. So the priority Q operations in particular insert delete max um how do they work if you're looking at uh such a a binary heap and for insert the good thing about this very rigid structure if you have a heap like this there's only one place where we can add the new element which is here that's the only spot a new element is allowed to go so it has to go there. Now, the value that this new element may have might violate the heap order. So, you may have to swim it up to repair that.

1:14 Um, let's see that in the example. Um, if I now go to an insert, I add a new element. I already passed this. So I'm adding a new element 79. There's only one place where it can possibly go, but it might mess up the heap property. Like in this case, I don't know if the numbers are big enough for you to read. 79 is the new element, and then there's 20 above it, which is famously not larger. So I might have to compare with my parent. And if that is in the wrong order, I need to swap them. And I just keep doing this up the tree until I'm happy until the element above me is larger. In this case, it happens right away. If I compare with my parent now, that's 86. And I'm already done.

2:17 Let's insert another one. The 47. This lands here and is already smaller than 79, which we just moved up. So that's fine. And it can stay. Maybe one more. Um, if we insert 15 here as a very small element all also stays where it is.

2:40 Oh, we're doing No, that was already delete max. Sorry. That's the insertion. You add a new element in the only place where you can and then you let it swim up. As long as the parent is strictly smaller, you swap with your parent.

3:18 There's one thing you should worry about in principle if we do that. If my new element here is now swapped with my parent say as we did it here, can that potentially mess up the other sub tree that hangs down here? Because I have to have the heat property before and after everywhere in the tree. Now let me maybe draw this a bit higher up in the tree. Suppose we have swapped these two. Could I mess up this arc? >> Yep.

4:06 >> Yeah, that's exactly right. So, you cannot create a new conflict because what was here before was already larger than anything in this sub tree and now we're replacing it with something even larger. So, it cannot violate this. which means as long as you follow up your path to the root and swap if needed, then you're never going to create problems in other parts of the tree. That's of course important otherwise we would maybe have to cascade all these changes elsewhere. Okay, that's that's really all there is to insert. And um in algorithm data structures, we would then have precise code in all the details. I'll skip that here.

4:49 The second operation is deleting the maximum. And how would you do that? Again, you have your heap. We know where the maximum is. It's easy to find. It has to be in the root. So the finding the maximum part is is trivial. But uh we have to somehow get it out there. And I can't really delete the root. The only element I'm allowed to delete is the last element here in the array. So uh I have to somehow get rid of this one instead. So the first step is to swap this last element with the root. Then I can at least get rid of the of the maximum. But of course I've now put something into the root that previously was at the bottom. Chances are this messed up the heap order again. So again I have to repair that. And this time instead of swimming up we sink down. We have something in the root that is is too heavy and so we compare we have to repair this. Now in general you have some some note here. This is too small.

6:01 So we have to move it down. But we have two children. So we have two choices where to move down to. But we don't really have a choice. Uh right. I compare the two children and I have to take the larger of the two up otherwise I immediately get a contradiction with the other one. So again really there's not much of a ch of a choice. I need one extra comparison. First compare the children then compare the larger of the children with the note in the root and potentially this also has to escalate down.

6:35 Uh let's see this here. So um I want to delete the maximum 98. That swaps it down. So then I can get rid of it. But I have to repair the heap. So 15 here is too small. The larger of the two children is 96. So I'm going to swap the 15 with 96. Now I'm not done because 15 is also smaller than the children there. So uh again I find the larger child 92 the left one and I have to repeat it again. Swap it down there. I'm still not done. 15 is a rather small number. So this time uh the larger child is is the right one.

7:34 But eventually I'm going to reach the leaf level and at the latest at this point I can stop [snorts] and then I can properly remove my original route.

7:47 Okay. So here again um we have to make sure that when we move down one part of the tree we don't mess up any other part of the tree. But the point is all the other parts of the tree, if we're replacing the root with something, it previously was fine further down. This part was okay before we changed anything. And we make sure that what we put here as the root is at least as big was as what we had before. Uh either we um either we continue bubbling down if this is too small or we're on the other side and then we've not changed that that root of this sub tree.

8:44 Uh the last operation I want to discuss briefly there's also delete uh the the decrease key operation or increase key. If you tell me this task should have a different priority. Now you can do the same swim up and swim down operations. You locate the element you want to change, you change its priority and then it will either be too small or too big and then it moves up or down by precisely the same two methods. Um, another interesting one is how to construct a heap when you're given a complete list of operation of of uh elements already with their priorities. uh what you could do is just inserting them one after the other from say starting from an empty heap. That works but you can actually do something that is faster and that's why we have this special operation for construction. Uh we start with we just put the elements in in an array and we start building the heap bottom up.

9:45 In a way, you're starting with these singleton elements and then you build little heaps of of three elements each. Let me draw all the elements first. Um, you build these heaps each time by calling sync on the root. The root might be too small for the current structure. So on these little tree heaplets on three elements, it might only sync down one position. So suppose you've done this for all these size three heaps. Now you want to do it on the next larger level.

10:29 You know that this is already a proper heap and this is a proper heap. So the maxima of these three elements is in the root respectively. So I'm going to call sync on the root of this seven element heap. now and it'll pick the larger of those two. Unless this is already larger than all of these. Uh I'm going to pick the larger of these two and swap it with that which may me uh move my element down here. And then I'm in the same situation as if I was just replacing the root with a new element. Right? I've taken what previously was a heap. I've changed the root. So I might have to further sync down. But I'm not going to mess up more than that. I follow one path down for each of these sync calls. That is all.

11:23 Again, um not that it really needs it, but let's have a a quick iteration drawn out. So at each position here, you're building the next larger little heap by calling sync on the root. For these three element mini heaps, not much happens. Uh here you may have a slightly smaller a slightly longer procedure to go all the way down to the leaves. And you do this once per vertex or per per node.

11:54 And once you've done that, you've built a a proper heap. Now, how much does this cost to do that? Well, as much as it costs to call sync on every uh position, right? um intuitively and let me make this um on a bigger example.

12:26 Intuitively, you should have most of the calls on very small trees. Half of the elements, after all, are on this level here or below. And so all of these cost almost nothing. just one step down maybe and then there's half of those that are on one level above that cost one extra and even further fewer each time you go up a level which costs one more you have the number of elements that you have to pay for. So maybe you can already guess that this is going to be fairly cheap and the cont dominant contribution will come from the lowest levels which pay constant each and that's also what the um what the result in the end is. Uh let me first show you this in kind of the the pictorial way. This we can get a little bigger. Okay, maybe not because the layout is messed up.

13:41 I'm so much zoomed in. I don't see where I'm I wanted this bigger. Okay. It doesn't really get the bigger bigger. Let I'll stay uh at this level. Um still struggling with this a bit. So we have here a table of the levels top to bottom. How many nodes in our heap are at that level? Uh it's the tiny one on the side. We have one node at level zero, two nodes at level one. That's what what you see in this column. And another nine in the last level. uh what they pay for a sync is the length of the path from this node downwards. That's five for the topmost because 1 2 3 4 5 is the number of edges it may have to go travel downwards and it drops by one as as I go one level down. Um if I multiply these two things that's the number of nodes times this cost.

14:47 That's an upper bound for what I have to pay. This works out to be 2 to the L, the number of nodes on this level times H minus L. That's the number of steps I have to go down. Um here you see the numbers work out properly if I go all the way to the end. So uh that's the the actual the actual cost that we had compared to the worst case. We'll just use this upper bound and try to work out what that is as a closed form. And it's spelled out on the slide in a bit more legible font. Let me first show you that.

15:32 So um the number of uh nodes first of all let's work out how tall this this tree has to be. Um, I think you may know from the top of your head that it's log base 2 of n. Um, but a bit more precisely, if you sum up how many notes you can squeeze on these levels, if you make all of the levels above the last one full, that's the sum of the powers of two up to some maximal level k. And that works out precisely to be the next power of 2 minus one. So if you want um a binary heap of uh for n elements, the height you need is the smallest k so that this this sum here is at least n. I need to fit n elements in. How tall do I have to make the tree for that? Well, precisely so that this inequality is fulfilled.

16:30 And that means um height is log base 2 of n. Okay. Okay, that's that's the analysis of the uh of the other construction of the other operations. Um uh that of course is also uh useful to state each of these essentially follow one path down or up. Insert swims one path up from this position where we inserted. Delete max takes the roots, swaps it with one element, and then has to trickle that sync that one down. That takes also h steps at most if h is the height of the tree. And for the construction algorithm we've just seen, we have this sum of uh one times the root may have to travel down age levels, two times, 1 - 1, and so on. That's in the table on the animation. And that's the closed form upper bound, right? have so many nodes on level L 2 to the L and H minus L is how far do they still have to sink down. You can rewrite this sum and um by essentially some summing in reverse and splitting the 2 to the H minus L like this. You can pull this common factor out that doesn't depend on I but you're left with this sum over I / 2 to the I.

18:00 Intuitively again this is almost like the geometric series. So it's maybe expected that it is upper bounded by a constant and it is bounded by two. One option would be to go to your most trusted source for such summations the TCS cheat sheet. And of course it will have this formula somewhere if you know how to find it. Uh it's basically hiding behind behind this one.

18:34 if you put C to 1/2. Now here for this specific case there's a a cuter uh graphical proof. I wanted to briefly show you this. I think it's it's right rather memorable. So we're summing up these terms here. I divided 2 to the I [snorts] and um what you see here in in red is this sum and then what you see subtracted is the geometrics is is the same sum shifted by one. So it's half of that where I take each command and divide it by two.

19:31 No, I don't get to click this. Let me use the keyboard. So this is take the same sum divide it by two and shift the sumance one level down. So I'm now taking the sum s that I want and I subtract half of it. So I get half of my result. Now um the leftovers what is in green here completely fits in a bar of size one because it is the geometric series. Here we started with one started with 1/2. Sorry. Here we started also with 1/2 but we subtracted the half of the previous. So we're left with a quarter. Here we started with 3/8s and we subtracted a quarter. Here we started with a quarter and subtract four 416 and we we subtracted. So we're at whatever that uh that is an eighth. And so what you sum up here is precisely the geometric series which sums up to one. What that means is the red thing minus the blue thing is one in the limit. But the red thing was two times the blue thing.

20:59 Well, uh the the blue thing is half the red thing. So the red thing is two. Okay, you can um I I'll show you the link and you can go over it if you find it uh helpful. The other option of course is algebraic. You can pick up the formula from the TCS cheat sheet and just plug it in the same result. Uh you can also see this as the element wise derivative of the geometric series. This is another cute way to memorize this. If you want to evaluate this sum i from 0 to infinity, let's call that um a of set of of this c as if it was a function in a variable. Then you can do things like taking derivatives which in a sum takes the derivative termwise. So what's the derivative of c to the i? well i * c to the i minus one. That's taking the derivative of a polomial as you did in kindergarten or high school.

22:07 And then that is eerily close to our sum here. If you set c to 1/2 is only shifted. So this our sum here I * 12 to the I I'm upper bounding this this finite sum with the one that goes up to infinity. This is just 12 times this guy a prime of 12. And um if that's the derivative, you can also take the derivative here. And uh this we already know is 1 / 1 - c. So you can take the derivative in in this closed form and it just works. It gives the correct result. So what's the derivative of the closed form? Well, it's 1 minus c to the minus1. Right? So if you take the derivative there, it's minus one. And then the derivative of this thing and the inner derivative I guess cancels the um the minus you can also write this as 1 over 1 - c ^2 and that was the formula on the cheat sheet. Okay. So if you're you can pick >> [snorts] >> uh there's option one just look it up on the cheat sheet. Option two, the algebraic approach. And option three, the uh intuitive bars fly around approach.

23:40 Sometimes um things can be solved different ways. Now uh let me stress one thing that kind of may may have been lost a little bit in all this math. The overall number of steps for building the heap bottom up is just two steps down per element. So really the intuitive version from before the dominant part is what happens at the low level is precisely right and it's even with the constant factor is very very close to this constant per element is even a two. So constructing heaps bottom up like this is very cheap. There's linear time as opposed to n login if you did n times an insertion.

24:23 And here are all the other operations. Um,