Video 2-4: §2.4 Operations on binary heaps

0:01 let me show you in the next subsection very briefly how you do operations on heaps and this again will be I really Zoom through this and the videos do it in much more detail with full Java code and so on if you want to see it in a bit more detail for insert uh let's just look at our example and and do one if I want to insert a new element in the Heap let's say we insert 86 68

0:34 because of the shape constraint for the Heap there's really only one way it one place in the Heap where it can go and that's here as the next uh

0:43 Leaf uh as the child of 40 that's the only place it can go and then we basically have to repair the shape to look like that there's no other option and that's what makes it easy but of course uh this violates the Heap order potentially like in this case uh we don't have this um let me get rid of the blue part um we have a violation here in that we don't have the parent be bigger so what do we do we swap those

1:31 briefly the 40 moves down 68 moves here now we have another violation here right this also is in the wrong order so we have to do it again again we have a violation so we swap it with the

1:58 parent if we do that here we have the 66 down here and then the 68 the new element is up here I want that black no okay try again I'll do it later uh and that that's okay then now the order here is the right way and the order down there is also the right way now notice that we can never create problems for the other branches of the tree because we previously had let's take for example this

2:40 one we previously had here a value that was smaller than 66 and we replace it with something that's even bigger so we cannot create a violation in the other branches so all we ever have to do is swap up on the path towards the root and because that's bounded by the height and the height is uh log rithmic in N that will be the running time in the end so we do

3:22 times okay so that was insert um let's suppose we want to remove something and maybe we can start from this one H okay sorry it's just a a little buck in that

3:45 software we can't delete arbitrary things but we can delete the maximum that's the key other operation that a priority queue is supposed to support so let's try that here and I'll I'll clear up a little bit with these things

4:09 needed ah I really want those black all right so we can delete the maximum we already know where the maximum is it's in the root so uh deleting it is not so not so hard we just remove it but now we have a gap in the tree so we can't really leave it like this it's not a v valid Heap so we have to put some element there now again the Heap shape means if I want to shrink the heat by one element I know what shape it's going to have to have I have to take away this element in the last layer the rightmost so what can I do well let's just take this element and stuck it in the

5:00 root and I wish I had left the copy of the initial state so let's uh add that here and again my red numbers okay they'll come haunt me I'll do the fix up later so uh that was the original state now we put the 40 up there great so the shape is fine but we screwed up the Heap order so we can't leave it like that now in this time this time is a bit more tricky because we have two children and we could have screwed up both like in this case there's a violation on this side and on this side and if we're not careful we create followup problems so what we have to do is first find the larger of the two children in this case 70 is larger and so among those three clearly 70 should be in the root because it's the largest of the three and so we'll do that

6:11 okay easy so 70 goes in the root 40 goes down here now we have repaired this one and that also means all the left sub tree will be fine because we haven't touched it but the right sub tree might have the same problem recursively so this the topmost of course is fine we just made that so uh but we could have violations here in this case we only have one violation but we could have both so we do the same again we find what's the larger of the two children and swap that with the element we just moved

6:52 down H okay there's a bug in the software where sometimes if you do things with the pen it doesn't register okay 40 is up here no sorry was right 70 is up here what am I doing and then I swap the 55 this place and the 40 moves down and then I'm done because I've reached the bottom layer there can be no more violations further

7:23 down that's the the key operations in a binary Heap insert and delete Max I'll very briefly comment on construction from scratch if you have a list of elements already given if you have n elements that you want to build a heap for you can do it by inserting it one after the other but there's a faster way so if you do it one after the other we haven't talked about the height of heaps in very much detail but I mentioned that it's logarithmic in in N it's basically log n + one uh so you will get a running time in total for the N inserts of n * log n uh instead uh there's a smarter way to do it um which is a little a little tricky so let me try to um just draw an example um we take our elements and we first build out of three elements little Heap plets tiny heaps and we do this all across the way and these are built like standard heaps so um always the largest of the three elements has to go into the root okay so now I'll just draw this uh box around them to indicate that these are little

8:49 heaps now um it's a bit silly for three elements to do it that way but I could reuse this same code that we've the same algorithm we've designed for the delete Max by um just taking arbitrary numbers putting them in these positions and then calling on the root this function sync uh that's what we've done here I didn't mention the name but what we've done with the 40 is we let it sink down until it reaches its final landing position and that's what the 40 did it sank down in the Heap in this case all the way down so we can do that here we call sync on this one sync on this this one then sync on this one and so on then we have tiny little heets of three elements each now we take two of these tiny heets and build an ele uh seven element Heap by again adding one more element and calling

9:55 sync and the way that this is better than successive insert is because we reuse that these are two two heaps already and I guess you already see where this goes in this example I have have to do it one more

10:13 time and then I have one big Heap containing everything okay I'm running out of space down here so there's one more call to sync at the top now I'm calling a lot of syncs uh why is that any better than doing syncs with insert it looks like this is not so different uh the key to see why it's better is most of the sinks half of the sync calls are at the at the bottom level where you just go one step down then from the remaining half is one level up and so on and so forth so the bulk of the work is done on tiny little Heap plets and uh you only have a few calls that syn down a lot of the tree and that's very different from end times insert

11:09 um let me briefly comment on this and maybe skip the analysis of uh of the construction so the height is um just to Define this properly the height of a tree and it doesn't need to be a binary tree it could be some arbitrary thing uh the height is just the longest path from the root to any Leaf we have these levels of elements at the same distance from the root and we usually start with level zero then one two and so on so the height could be um could be defined as the maximum level or the number of edges on the path from the route to a deepest leeve so that's the height this case four

12:04 and the depth again so all this counting edges that's the thing you have to remember and we start at zero so this element would be at depth to because there's two steps I have to take down um if I analyze how many nodes I can stuff in a binary tree I sum up powers of two because I start with one then everything has two children so doubles at each step in a in a complete binary tree whenever I go one level down I double what I had on the previous

12:44 level and so if you sum those up you get the total number of nodes in the first K levels and if you want to get that to match n if you want to have space for n items that means you need so many

13:03 so I just want to want to have the concrete numbers on the slid uh for insert what we do is we have this one element that we stick at the bottom and then it swims up so for every level that we swim up we have one comparison but that's it for sync almost the same but we need two comparisons because we first have to find which of the two children is bigger and then do the comparison if we have to swap so we need the comparison of the two children and of the element with the larer child so it's 2 AG um and for the construction from scratch you can work out that the total cost is four n comparisons at most which is better than n log n um and I'll skip the details this is essentially what I said before spelled out uh formally most of these sync calls are on small small heaps and if you sum that up it turns out the overall cost is just linear

14:06 that's all on binary heaps um here's a table of the full list of operations for the abstract data type and what running time heaps achieve that's something maybe uh to keep in mind uh the key key information is logarithmic time is what you need for insert and removing the maximal element I haven't talked about how to change the priority you can watch the videos it's very similar you can find a node and then change it and either swims down or SNS uh swims swims up or SNS down and the other operations are not hard hard to do