Video 2-4: §2.3 Binary heaps (part 2)

0:00 <Untitled Chapter 1>

0:03 we have some we have some a few comments left on binary heaps before we move on to binary search trees we talked last week about how we can insert a new element into a binary and so that worked basically by putting it into the only spot where it can go and then letting it swim up the heap repairing the heap order in the tree we also looked at how to delete the maximum in the heap it was easy to find it is always in the root then you take it out but then there's a gap and you have to fill this gap again there's only really one spot where an element can can be taken from so you take this 25 and put it in the root but that violates the heap property so again you let it sink down which means it's always swapped with the bigger of its children i'm stressing this again because um we still have to do the analysis of this part for the heap construction you can do n inserts but that would be slightly more expensive than what we can do a better heap construction algorithm is is this one where you start with individual elements take the half of the elements are in the leaves roughly and then you

1:24 add one to two of these make it a little heap of size three and you always let the the root of this new little heap sink down again then you have these little heaps of size three you do the same thing again put a new element as the new root of two of these and let it sink down do that again so you keep doubling roughly the size of these heaps each time and i already sketched this last week but we'll briefly touch on this again so that will give you overall linear linear cost

2:01 i wanted to make sure that this analysis part is is written up properly so here's that in slightly more detail again i think it's worth pointing out that there's two two notions in in heaps that we will use a lot that's the height of a tree which is simply the number of edges on the longest route to leaf path so let me just add a heap some the height makes sense for other types of trees so maybe let's add a note with some more m with some more children so obviously here the way i drew it the longest route to leaf path is this so here the height would be one two three four

2:02 Analysis

3:02 just to make that clear you could also define the height as the number of nodes on this path instead of the number of edges but that's that's one way that's the way i want to use it the second thing is the depth or the level of a node depth is probably clearer so i'll try to use this term but in the context of heaps depth level is a little more conventional

3:34 the depth is basically the length of the path from the root so the root has uh depth zero is at level zero then there's a level one um and um if you just connect them if you draw the tree nicely horizontally aligned then you can see the levels easily and here's another node on level four and that's that's it so uh that's the the two um the two terms that i wanted to introduce here and we'll use that in the analysis briefly for binary heaps um

4:14 one one nice thing that you can do with this is count how many notes do we have on the first k levels of a full binary tree so this is again heaps so forget about this tree on the side that was an example to illustrate the the first two concepts

4:31 for binary heaps we have this very special shape which was if you remember it was always of this type so there's always these full levels here they're completely filled with as many nodes as possible except for the last level which might be slightly smaller but if we uh just take the first k full levels then there will be exactly two to the l notes on level l because we start with one node on the root level and then it doubles each time because on the full in a full binary tree every node has exactly two children and if you sum that up you get another power of two just minus one uh that's just what it work what this sum works out to be and uh why is that useful we can invert this formula and solve it for the height so the height is the lowest level as you notice in this example here also a height is four and there's one node on level four

5:36 then the height can be calculated as the smallest case so that the number of nodes here exceeds n and so that you have enough space to fit all these nodes and that turns out to be just the binary logarithm of n so this is lg is my shorthand for log base 2. so that's just the log to base 2 of n and then round it down the floor function

6:07 okay uh with that preparation we can analyze heaps uh fairly easily first of all um for insert and delete max that's why i just went over the procedures again you just have one path that you follow for insert you let the element swim up so you swim up from a leaf all the way to the root potentially in the worst case you have to go up all the way um in many cases you can stop a little earlier if the element has already found its position so that's the most h steps up the tree at most age comparisons on the way for delete max we start at the root remember we have this gap then we fill it with an element from the leaf level but that has to sink down again so again at most h steps and

6:59 that's two comparisons each because you have to compare the two elements that the two children to decide which one is is replaced by the element that sinks down you can you can slightly improve on this uh by observing that most elements move down so you could speculatively first moved on all the way and then back up that turns out to be better on average but that's a minor optimization that i don't want to go into and finally for construct so um the cost of of this construction algorithm maybe let me show this picture again if if this is the final tree notice that what we did at the end is we let each node sink down from its position at some point in time during the construction so this one sank down when we combined these two three size three heaps into a size seven heap then we later combined it and oops this one might have ended up this this element that was at that position might end up somewhere completely different but the cost of all these construction steps will be the same as if each node is sinking down from its level um all the way to the to the leaf level that's the worst case

7:41 Heap construction

8:31 so if we go back to our analysis it means there's one element the root at level zero that has to sink potentially all the way down the entire height on the next level there's two elements and they have to sink down well height minus one steps at most next level four nodes but the height decreases etc so you get this sum and if you if you write this up we sum over the levels there's two to the l notes on that level and they have to sink down h minus l further steps before they reach the leaf level you can rewrite this sum by just summing in reverse and then this 2 to the h doesn't depend on i so you can pull it out of the sum and then you're left with this sum which again um there's a known closed formula for this you can ask well from alpha if you if you've never seen this but there's a simple upper bound you can just bounce upper bounded by two so that shows again a little more formally that the heap construction algorithm i sketched last time already really takes linear time in the worst case to construct the heap out of n elements

9:42 Binary heap summary

9:45 and that brings me to this summary slide that's just all the operations in a binary heap and the corresponding running time all running times are worst case um i think i omitted size you can also add the size by keeping track of the size just a counter you can you can implement this in constant time that's not too hard and then is empty can just be a check if the size is zero these are usually easy to get uh the key steps are insert delete max and change key which we didn't talk about but i think i mentioned last time if you have a pointer to an element you can change its priority and then depending on how it changed you can either let it swim up or sink down and then you repair it the heap property that concludes the section on binary heaps