Video 2-4: §2.4 Operations on binary heaps

0:00 <Untitled Chapter 1>

0:11 Insert

4:30 Binary heap example

4:43 Delete Max

8:16 blah blah blah i can see it here uh-huh okay it should work now thanks for letting me know ready yeah yeah uh the one time i wasn't watching i think that was the when i reconnected the

8:44 well there's always the recordings from last year they are very similar okay back to um to deletion in heaps or the sync operation we've put the 70 up here which picks this one violation to one child it actually fixes this violation too but it created potentially a new one over here

9:08 in this case the other child's fine but as i said before this is not good enough so we'll have to find another one around and move the bigger child up again

9:22 and so i think we can just just squeeze that here 70 moves to the root 55 is swapped here the 25 goes there and now uh all the edges are good again okay so we've uh repaired the heap order and removed one element from the heap that's how that works um i don't think i have a an example for changing the key changing the priority of a key but you can actually do it the same way you look where it currently is you change its key and then you let it swim up or down

10:11 Heap construction

10:13 there's the last thing i want to mention because this is um what separates the heaps from from binary search trees later we can create a heap from a given list of elements with given priorities and we can do this in linear time so there's a way to do it in n log n time by just repeatedly inserting the elements uh to analyze this you have to be a bit careful but you can say the second half of the insertions works on a heap that has at least n half elements already in it and so log of n half is basically log n but minus one so you only save one comparison each of those or one one step down uh we haven't talked about the the analysis in detail but those of you have seen this before the the quick message is this is this is slower than it needs to be there's a smarter way to build a heap if you start from a given list of of elements

11:24 that's to start with single elements and build the heap bottom up so you start with elements like this that is a heap of its own and there is some key in it that i'm not drawing okay and you do this for all the second half of your of your input make it a nice one let's say we have uh have exactly a the power of two is convenient

11:55 so these are heaps of height zero they're just a single element now i can fuse two of these together to a bigger heap by letting this element sink down

12:14 and i do this with the others as well i also let those sink down and then i have uh lots of little heaps of size three or high two height one okay

12:41 and i add another note to two of them and fuse them again by letting this one sink in the resulting heap and same here um and then one last time

13:07 you have another sink of that one of that one so these are all the original elements of the array right so the the singleton heaps you start building is just the second half of the elements then you take a few more elements that are from your your original list of elements and make them the roots of these three element uh heaps the little cherries and then you take two more elements to put as the new root of the fused heap of of the next height and so on that's the way this this algorithm works and we'll see that this this runs in in linear time

13:50 and that's even even though the last sink has to go all the way down but that's um let's separate the analysis and the algorithms i want to say a few words about about all of the operations and for that we need some terminology that i've been using already but i wanted to properly introduce it uh we say the height of a tree is the number of of edges on any on a the maximum number of edges on a route to leave path so if you have a heap if you have an arbitrary tree this doesn't even need to be a binary tree it could have any number of children

13:59 Analysis Height at binary heap

14:31 at some point then the height here is the number of edges on this path that's the longest so the height is four and the second notion is the concept of levels or depth and this is just all the nodes that have the same distance from the root these are on one level they've drawn nicely and the last one so there's level zero one two three four so you could also say the height is the maximal depth of any node

15:19 uh with that definition we can count how many nodes there are on a certain level now back to heaps binary heaps and complete binary trees so this is again on on binary heaps only

15:36 binary trees if you fill up the levels completely then the first level zero is just a single node level one is two children and it doubles each step right so you get a power of two so a

15:55 heat question you tend to use the level zero as important mostly whereas for a while you have to calculate the height of the depth you tend to calculate the overcoming top that's right um yeah okay so if you're given a tree that the levels are counted from the root downwards what we did in the heap construction is we built the the heap bottom up so we constructed the last level first but in the final heap i would still say this is level zero one two three in the in the final heap it's level three or depth three but i mean in between it used to be at a lower depth because it was just a collection of little it's always the definition is just for for a static tree once it's once it's finished uh and if you sum up the first k levels together so that's the total number of nodes in your binary tree then you sum up the first powers of two and that's as you may know geometric series etc that's the next larger power of two minus one and you can check this works out it starts with one then three which is four minus one then seven which is eight minus one uh what does this mean for binary heaps

17:10 if i want to put to put n elements in my heap i have to make sure that i'm filling levels completely right so i always stuff as many notes into the the levels as possible um and this formula says that's the the number of notes you get if you do that and i need that this number is at least n otherwise i can't put all my all my notes in this tree so what i want is this sum or rather this which is the same should be at least n and that turns out that uh the k that minimizes this so the smallest case so that this is true is log n round it down so a heap that contains n elements will have this height it will have level 0 up to this number why is that important it's important because the height of the tree dominates our running time in all the operations if you remember how insert worked you you put in this new element and you let it swim up you can only swim up one once per level you never go back down so you need eight steps at most it might stop early but in the worst case it goes up to the root and you use h comparisons

18:32 in this case as well if you remove the maximum it was slightly more complicated but still you let this sink down and it goes down one level each time so you do it most age such steps but the number of comparisons is twice that because we first compare the children and then we we check if we have to sink further down now the the construction from given from a given list of elements is the most interesting one and for that maybe we should go back to this slide we do one sink at the end

19:11 where we um let it sink in the entire final heap so this has roughly cost um log n or if we use the final the final height uh that's the that's the cost how many levels it has to sink down on this level we have two times a sing operation but they each only cost h minus one because the trees in which they sink are one less tall on the next level i have fourth four sinks but they're on h minus two high trees and you keep going like this until at the bottom level you have many sinks but they're all doing nothing okay they're just stopping immediately if you spell this out that's what it looks like so we have that's the root then we have two times h minus 1 and so on and so forth and then this is the last step where we have the bottom layer where we don't do anything anymore if you sum this up you can write it as this formula that's the the generic term sum from 0 up to h over all the levels and you can rewrite this sum like here i uh i summed in reverse then you can pull out this constant and this is um the derivative of a geometric series so

20:35 you can look up this sum is just at most two if you let h go to infinity it becomes exactly two that's the limit that's something you can ask well from alpha if you if you want to double check so the total cost for all these sinks together is two times this factor in front and remember if you if you plug in this log then 2 to the log that cancels again just to n so we need the cost for building the heap is is just this 4 times n so linear in the number of elements whereas if you did n times the insertion you would have in the second half after you've done the first half of insertions you have a heap that contains at least n half elements so it has height h minus 1 already and then you do n half more insertions with that height so that part already gives you n log n with some constant in front

21:42 Binary heap summary

21:44 that brings me to the summary of binary heaps that's all i want to say about this in this class we can construct them in linear time we can find the maximum right away the other operations are also easy and the others all have time dominated by the height which is logarithmic in n by the algorithms we've seen