Video 2-4: §2.4 Operations on binary heaps

0:00 <Untitled Chapter 1>

0:03 I've told you what a heap looks like now we want to do something useful with it and data structures are only really interesting if we can change them dynamically

0:12 so in this next subsection we'll look at the operations on binary heaps that allow them to implement all the priority queue operations and um I'll only very briefly explain the code and then Show an example and for more details I'll refer you to the extra material on the website all right so in particular I don't want to show detailed code I think it's uh for most of you it's repetition for the others it's probably too quick either way in the time that I have but the videos explain this lovely in in much more detail so how do we insert a new element uh if we if we take our Heap from before

0:57 if you look at this Heap and you want to insert a new element by the severe restrictions on the shapes that we allow there's only really one spot you can go with a new element namely on the last level the next next element here on this flush left so I don't know I inserted

1:20 68 now okay my drawing is is not so nice but this is of course the left child of 40. okay that's brilliant so the the shape is satisfied we have a new complete binary tree just one bigger but we messed up the Heap order because now this one's smaller than this one so we can't leave it like that and to conserve this so this is the other way around that's that's bad well let's say it's not like this um so what can we do well if two things are out of order we can just swap them exactly I think this is too big

2:11 I'll try to keep the intermediate stages on the on the slide so the first step would be swap the 68 up here and 40 goes down that certainly fixes this one let me get rid of this this blue part here because that's that's just uh confusing

2:38 now this is fixed now observe that the other child cannot be messed up by this we still have that the parent is bigger than than this child because it already was smaller than the 40 and we replaced 40 by something even bigger so it cannot possibly violate the condition after that okay and that's important because otherwise we would potentially have an endless number of violations that we create and so we don't we don't really fix anything but that's not the case uh the other sibling is not a problem in this case now we still aren't done because this is not true so we do another swap

3:48 you'll have to remember the order no ah cool I think I created a problem this one's too far out of the slide that I can't um mark it that way but I can grab it to the other tool

4:12 all right it's not the point to get perfectionist um I also copied the wrong one brilliant so more more effort to fix it so let's see we have the 40 already down here we had now swapped 66 to here and 68 ends up there and if you check now uh all the conditions are fine this is true this is still true and this is true I know this is also true now I see there's there's another thing we should think about uh when we swap those two now we did actually put something smaller here right that's potentially danger territory it's still in this case fine because if you look at what there was at the very beginning we know that the 66 is still bigger than the 40. so it was fine to put the 66 eventually up down here and it can't violate any of these links because they were fine before replace them with something that's only bigger so they're fine after so you see how this this is very naturally framed in terms of these preconditioned post conditions that we talked about for verification in many cases data structures have something like an invariant as well it's not a loop invariant necessarily it's more something maybe you can call it a structural

5:40 invariant so in our case we say a binary heap if you don't disturb it at the moment must be a complete binary tree and it must be Heap ordered and now every algorithm that we work with can use this as a precondition it can rely on this invariant to be in place and then you can prove correctness based on that that's exactly what we did why are these these green inequalities true well because the invariant guarantees though guarantees them indirectly

6:16 okay um so that's insert uh is this the same problem no here it works I want to comment on this on this uh name swim so uh people sometimes call this process letting that element swim up the Heap because you basically uh imagine this was some some bubble of of air in water and they would just Bubble Up the Heap uh swim up until to the point where it is uh denser than the parents but not less dense uh well until it has the the points in the sorted order of densities that's how liquids sort right all right that's insert

7:08 Delete Max

7:13 how do we deal with deleting the maximum so we've already said it's really easy to find the maximum um okay that's the one with the with the broken 68 but let's just get rid of this again

7:31 it's never it's never been there you haven't seen it right it's easy to find the maximum it's the 87 no deal it's it's in the root so we can just take it out

7:49 and we want to store this in a temporary variable and return it at the end right that's that's all right uh but we've created a hole in our in our fine Heap and holes are not allowed right this is uh we can't accumulate holes not not part of the invariant so again we have to re-establish our invariant and there's two things that are broken the shape is broken and potentially the Heap order well depending on how that interacts with holes the first thing is the the shape let's fix that again because that's easy the only way to make the Heap one smaller is by removing this this slot right it's the only way to go now we have this element 25 there and we have a hole up there sounds natural to just do the obvious thing so let's stick no that was not the one

9:10 what is this it's always a new bug let's try a different tool that seems to work don't ask me why it's the beauty of Open Source software sometimes so let's take the 25 and just stick it in the route but I guess you can already see that this is not really the solution at least not the final solution

9:48 so the problem now is we we repaired the shape but we again violate the Heap order um as you can see here so this is no longer true no longer true so we even messed it up with both children so what do we do now we'll have to some somehow repair this by swaps again but we have two children that we could potentially Swap this this new root with and we have to be a bit careful because we have to do the right one so what we do next is We compare the two children and remember the invariant doesn't tell us anything there could be in either order the bigger could be left or right we don't require anything in this case this one is the bigger one we want the bigger ones high up so natural operation is to swap these two okay so let's do that and see how far that gets us

11:03 thank you so we fixed this one we fixed this one uh we fixed this one we fixed this one but we potentially created trouble because we replaced the big element by a small one and this time the invariant is not going to save us yet and indeed we have a violation here right

11:36 so we have to keep going do another swap again we compare the two children 25 is the bigger among the two children so we swap it with that one

12:12 now in this time we're fine just because we ran out of children that we could potentially mess up and that's the usual way how this how this uh ends we just trickle down the Heap until we've reached the leaf level and then there's no more children that could be out of order

12:36 the important bit was to swap with the larger of the two of the two siblings right that's how we can remove the largest in a heap the last operation I want to present in some detail then the rest I'll just claim are similar is how to construct the Heap if you start with a given list of elements now what you could do is you could start build a heap from nothing build an empty Heap and then insert them one after the other uh we'll see that this this takes n log n time overall uh after the analysis uh you will you will be able to see that for now you may just be a may just believe it so uh that's okay but we can do better a smarter way is to start with a little little tiny heaps

13:33 and um use the procedure we've just used in in delete Max to fix them up into bigger ones I think this is easiest Illustrated uh again in a schematic example I won't do the the numbers this time

13:58 so we take the roughly the last half of the elements and put them As Leaves of the eventual tree there I'll just call these little tiny heaps each one is a little tiny Heap on its own

14:17 it has the shape of a complete binary tree and it's Heap ordered because there's just a single node there's nothing to really go wrong now I'll take the next few elements and put them here

14:37 and now I'd like to claim that we can make these into little heaps of three elements each so what we do is we put the element there and we let that one sink down so we say sync on this one sync on this one all the roots are just sinking down once

15:10 now for three elements we can just figure this out in our heads right the you take this the bigger of the two children unless the root already is bigger so the the maximum of these three elements is either the root of one of the two children if it's the root we're done if it's one of the children we take the bigger of the one put them in the root and swap the root down and that's all right maybe a bit quick but so far that's easy now the tricky bit is that you can do this inductively so you can put the next two elements here and make these into even bigger heaps again with a single sink

15:51 so one sink here one sink there and then you have heaps of twice the size roughly now why does that work it works because these parts are already heaps they're already Heap ordered so the largest of this little Heap is in the root the largest of this little Heap is in the root so the largest of this bigger Heap is either this new element or this or this and so the sync can find that one if it's in the root build leave it there and are happy if it's one of these two we swap it with the root and bring the other element down and recursively fix that one that way a single single sync operation repairs uh turns turns these two smaller heaps into one of double the size and if you do that one last time where the last element then uh we have one big Heap

16:54 now in this case it worked out nicely because I made the numbers to work out nicely if if you don't have the appropriate number of elements then some of the leaf Parts on the right would be smaller so some of these heaps are are empty but it doesn't actually change the algorithm you just merge smaller heaps into bigger ones and call one sink

17:18 now the sinks are not for free and some of the sinks like the last one has to go all the way down so you might wonder if that's any cheaper at all but it turns out it is

17:32 because you can you can analyze this level by level um I wonder if I can squeeze that on this slide my drawing skills really get in the way today

18:04 Heap construction

18:44 uh what I wanted to do is annotate this with the costs so now we have a little space and we sink down uh in this case the height of the final Heap

19:10 so the cost of the sink is basically the height in each in each step we do two comparisons we find the larger of the two children and we do the swap and we have to check if the parent is actually larger than the larger child

19:25 on the second level we have two times a sync operation but on a one smaller Heap so one less one less tall if you go one level further down we have four times this but H minus two so we go all the way down and on the last level we have roughly in half and there's a zero left at the very last level really do nothing on the levels above we do one or two and if you sum up these things uh you see that the majority of the calls for sync is really at this low level where they are a constant time so if you sum this up that adds up to linear in the total thing so the overall time is linear instead of n log n

20:30 Analysis

20:30 I have that written up properly on the next slide so let's let's Briefly summarize the the analysis I did informally uh first of all what is the height of a tree I think you have an intuitive understanding maybe but what I really want wanted to mean in this module is the number of edges on any route to Leaf path and I want the longest the longest such path so you can go from the from the roots any path down and you count the number of edges you take the largest number you can get at by walking down to some Leaf that's the height of the tree okay which also has it means a node with just a single tree with a single node has height zero

21:25 this one has height one this has height 2 and so on uh conversely we talk about the the depth or level of a node as how many edges do I have to go down from the root to reach that element so this is level zero that's level one that's level two and so on

21:59 and uh now you can count how many notes can I have on a certain level uh in particular if these are full right then um you have one node on level zero and for every node on level on the previous level you have two children on the next level if everything's full so that means we have

22:27 on level L we have 2 to the L no it's if it's full all right if you insert 0 then that's one if you insert one that's two notes and so on so if you sum up the first L levels and they're all full that's this sum which evaluates to the K plus 1 minus 1. okay almost the next Power of Two so the height of a binary Heap can be calculated by inverting this this formula in a way we are looking for the smallest case so that the number of nodes that can fit in with K levels is at least n that's my height because I need to put the notes somewhere I might have some space on the right remember um but I need to need to put in at least n and if you invert that it means that uh the height of this Heap is is log n rounded down remember height is counting the number of edges so it actually has eight plus one levels right you start counting at zero with the levels all right that's terminology uh I'm just going over this slowly because uh we'll use that for other bits

23:45 and with that um with that prepared we can finish the analysis of all the operations insert was basically dominated by swimming up we put the new element and the only spot it can go and then it swims up and every step brings the new element one level up or some other element one level up uh yeah here actually has to be the new one and so on after at most H steps H the height of the of the Heap we necessarily stop we're deleting the maximum is the opposite We sync down

24:21 um again we have H steps of syncing at most but the number of comparisons here is is twice that because we need to compare the children and we need to compare the parent and the child to see if we're done

24:35 and finally the uh the construction I've already shown you informally how this uh summarizes that's that's the same sum written up properly uh you can write this formally as this um

24:49 and the rest is basically something that you would learn in some discrete math class so I'll I'll basically skip that here or pretend that you know it uh it's tricks like summing in Reverse pulling common factors out and then looking up sums like this uh on some formula sheet well from alpha is something that's useful for that as well

25:18 last slide is summary of all the operations if you work out what they work in terms of n these are the running times for all the operations in in binary heaps