Video 2-3: §2.3 Binary heaps (part 1)

0:00 <Untitled Chapter 1>

0:03 slightly more interesting in the next subsection i want to talk about priority queues one of the building blocks for many algorithms and data structures and you will see some examples later in this class as well so i want to briefly cover these um also it was one of the the topics that was um were half or less than than you have seen it before

0:04 Priority Queues

0:29 i want to start off with a little question just to see again how well exactly you know these things there you go but i don't really want to wait for your answers at the moment

0:49 Heap Ordered Trees

0:50 so the question is about about heap ordered trees this is different from priority queues the priority queue is really the abstract data type and i put here this uh whatever it is gin and tonic in the plane um you can sometimes have people with different priorities you can have a business class first class passengers and if if you're traveling and waiting for boarding at the airport it might happen that there's not the standard queue where everyone just enters at the end but some people are allowed to jump the queue and have priority boarding so this is uh this that explains the picture just to keep that um memorable for you maybe the priority queue abstract data type is a back where the items have priorities and that that influences the order in which they are retrieved from the back but to be a little more specific i listed the operations here because we will need some of these for the tutorials as well we can construct a priority queue from a given number of elements if they're stored in array that's the most convenient way and you can also start with an empty priority queue and then insert elements with a certain priority the difference is that the construction from a given set of elements

2:21 might be cheaper because you can do a bulk insert instead of inserting them one at a time and we'll see that precisely this happens for binary heaps then there's an operation max like top in the stack that is just retrieving the the item that would be deleted next so that's the item with the largest priority and you can delete the maximum which removes it and also returns it sometimes you also need an operation to change a key or to delete an element with um a pointer well i won't obsess about this too much i just want to mention for those of you who have seen it before you usually assume that the element whose key you're changing is given to you by a pointer into the data structure so you somehow keep track of where this is and you can jump right to that element that's something that's not sometimes not stressed too much in theory classes but if you implement binary search binary heaps and try to do the change key you need to know where the element is maybe this will make more sense in 20 minutes and we can sometimes do a check for empty but that's easy so priority queues turn out to be a fundamental building block for graph algorithms

3:46 for coding algorithms that we'll see and they often simplify how you can specify an algorithm so they are really fundamental and widely used now a priority queue is really not one adt but two because um i specified here everything for maximum but sometimes it's more convenient to have the minimum instead of max so same game it's just flipping everything around the theoretician would say wow you just invert the order whenever you have two elements you define the order that gives exactly the opposite answer and that's fine but uh in

4:28 practice you sometimes just want to not confuse the user by using the exact opposite terminology so both exist and it to make it a little confusing for students some textbooks use the min oriented version some the max one i use the one max oriented will be what we use in this um in this unit because that's what uh the the videos i mentioned on the website also use so to be consistent with those

5:02 um all right i haven't started the other question so let's first go to that one and well we'll do that differently this time uh i will just stop the question now i'll show you the results

5:22 but we will come back to this um later if if we start with an empty priority queue and insert these numbers and then do a deletemin what happens i guess you guys were still busy with reading the binary heap answers because they were long and lots of text

6:32 and to make it a little more challenging notice i use delete min here so this is the min oriented version uh despite what i said in this unit we want to use the delete min this question at the delete max this question uses the delete min that was not supposed to be a trick question um probably should have changed it to the lead max but let's keep it as it is for now okay um yeah most most of you got that right um i got a few people confused with delete max i think um and uh of course it's it's one if this is the natural order if you insert these elements into the priority queue delete min will remove the smallest of those and return it and that's that's the one that's um why that's the answer

7:39 Implement Priority Queues

7:39 and let's now look at how we can implement priority queues first of all we can do uh very elementary things we can keep an unordered list of items then it's it's cheap to insert but for delete max we have to scan the entire list not very interesting the opposite is we can keep a sorted list then we can easily delete the max because it's always at one end say you're sort of decreasing so uh

8:07 this is this is confusing decreasing like that i'm mirrored so uh you have the the smallest element at the beginning uh but insertion can take linear time because you have to move elements around i'm i'm assuming it's a well if it's an array you have to move elements if it's a linked list you have to find the insertion position and you can only do this by walking through the list so both of these are not really good but they might be uh inspiration for looking at the better solutions the problem here was we either we went to two extremes either not sorted at all or completely sorted not sorted at all was good for insert completely sorted was good for delete max maybe we want to do something in the middle slightly sorted so what's a slightly sorted list a slightly sorted list is a binary heap in a way that's one one way to see it and there's really no good there's really two ways how you can define a heap a more intuitive one is the tree view that i will mostly use but for implementations there's an array view which is also useful let's look at the the tree view first and that comes back uh to the question i post at the beginning

9:21 Tree View

9:29 a heap is a tree where um the shape is restricted to a complete binary tree and i will use usually draw these like this the reason for that is a complete binary tree means it has full levels

9:50 except for maybe the last level now this is a bit this one should be a little closer to that so that's the left child that's a complete binary tree so a heap in our setting a binary heap has to have this shape it's a binary tree but it has to have this very specific shape all levels full and the last level as far to the left as possible and heap ordered which means that the keys whenever i compare two keys and one is the father of the other the parent of the other i should really use the gender neutral version here doesn't matter um so if the parent has a key and the child has a key then the parent key must be bigger

10:46 we can store such a key store such a tree conveniently in an array because it has this very specific shape and what you do for that is you essentially walk through the tree in this way level by level

11:06 so sometimes called level order traversal and then you assign indices in the array like so you start with one then two three four five six seven eight nine ten and so on if the tree was bigger and then it turns out that magically if you do that

11:36 the array represents a valid heap if and only if for every index we have this condition that the value at this index is smaller is at most the value of the index where you take i divided by two and round down i suppose you have seen either one of these two conditions and maybe even both are equivalent in terms of defining things usually array view again as i said is for implementing and the tree view is to make sense of what's happening

12:10 so i want to show a concrete example just so that we're on the same page what i mean with the heap order and so here's just a specific example that i made up

12:36 and as you can see it has the shape that i drew before it's always of this almost complete binary tree and whenever we follow a path down say we go like this one then we always have this is less that's a bit too fat

13:04 this is less uh okay i'm drawing this on like that whenever you follow a path from the root down or wherever you started the tree if you follow a path downwards in the tree the keys only get smaller all right um

13:20 let me take a copy of this with me for later because i will need to draw such trees again why do we like exactly this shape um i want to motivate this a little bit before we move on you will also i mean the the other answer one answer to this question would be that's how it is and that's how it works

13:49 but there's a better answer to that and i have a couple of reasons here to motivate it a bit one is there's only one possible tree shape and that makes life simple also complete binary trees are have minimal height among all binary trees because you put nodes as high up in the tree as possible so you fill them up in the top part of the tree as long as that's possible so that they will have minimal height and we'll see that the operations are essentially bounded by the height of the tree and last by fixing this specific shape we have a very simple formula for embedding nodes in um in an array remember this level order traversal was giving rise to this very nice formula for the heap property and similarly you can navigate from a node to its parent that's what we used in that formula you can navigate to the parent by uh going to the number divided by two rounded down and you can also go ahead and go in the opposite direction

15:00 and uh why do we like uh see if i can get out of the way here a bit uh why do we like heap ordered well first the maximum is always at the root so uh the maximum function is trivial to implement and uh also it's it's sorted along the paths of the tree but leaves a lot of um a lot of flexibility in how to assign keys uh how to or how to mix the paths in this tree so it's only very slightly sorted really and that that will be useful in maintaining this in operations

15:02 Why Do We Like Heap Ordered

15:42 okay so uh let me just reveal the answers to this old question um no that was not the one sorry this is the one so you can you can see this on the side now and um

16:03 i like to ask this question precisely because as you can see a couple of people mixed it up with the second answer and that's a typical confusion because the two concepts are so similar it's often that people confuse it with binary search tree properties we'll come to that but this is really what what heaps are about

16:32 okay in the remaining time i want to sketch how you can do operations on binary heaps so for that i'll i'll use my little example heap here make it a little smaller and maybe we can get rid of the blue part which we don't really need

17:04 all right so here's here's our um here's our binary heap how can we insert a new element say uh we want to insert the number was a nice example

17:07 Insert a New Element

17:21 uh 68 say because uh of the shape i don't want to write this in red um the shape means there's only really one possible position for this new key to go

17:47 and that's uh right here so we can only really put the 68 here which means it would connect to this tree like that because any other position would violate the shape constraint so

18:04 we would rewire this like that and now we have a problem with the heap property because the the heap order is violated potentially in this case it is because 68 is bigger so uh what can we do well we take this thing

18:39 i think i need to make it a little smaller i hope it's still big enough for you to see so that was the initial state now we can't really leave it in that state

18:57 because the heap order is violated here so we have this problem here so what we do is we flip those two numbers now i don't know somehow the the great thing that i drew here nicely is is lost

19:33 and try that thereby to repair the heap property so we let this we let this item 68 so at this point we're a little better this is fine but here the violation still exists so we have to continue and do this one more time

20:22 and the 66 from before and now this is also is also fine and this is fine so at that point we have reestablished the heap variant and uh we're good this is a valid heap again and we've inserted this new item um one thing that uh is important at this stage is let's see if i can squeeze myself here while you do this um you swap a larger number up so this was fine before and it's also fine afterwards whenever you do this the other children of affected nodes they're never um they will never violate the heap property so this is never an issue

21:11 uh that was that was insert um as always if you have questions shoot them up so maybe this is a good time to discuss them um let me stop the poll now so we can see the the questions

21:42 um let's see if i made a mistake for the first question uh yeah 85 is a 55. i miscopied from my sheet thanks for pointing that out could i copy the wrong version 500 times

22:10 yeah but now for the record let's also fix it up here and let's copy that one again even though it means i have to delete the blue part again

22:32 yeah thanks for pointing that out and [Music] for priority queues would you often plot a graph with items on the x-axis and priorities on the y-axis i'm not sure if what the question hints at you can do this it's sometimes insightful the the problem is x might not be a number it might not be comparable so the priorities have to be ordered so that you can talk about what is what is a large priority what's a small one the items that we insert in x they need not be comparable so sometimes you cannot draw them on the on the axis but we will occasionally use that maybe

23:20 um are you saying that the leaf is smaller than the parent yes that's what i'm saying except that leaf is generic is a special case um maybe this was the the mistake from the slides

23:34 any child is smaller than its parent that's what i'm what i'm saying for the heap property all right um that was insert if you have questions to insert put them in the in the q a

23:54 uh then the second operation that we want to look at is how to delete the maximum i promised to stay consistent to the uh the book so this uh will be delete maximum not delete minimum uh let's get my favorite tree here again good that i changed this and let's move these away and

24:25 keep hold of it now we want to make this smaller a bit smaller again now deletion of the maximum element we want to get rid of the biggest element finding it is very easy of course the max has to be at the root so it's right here and returning that would be easy the problem now is that we want to delete it so we store 86 to return it and now we want to vacate this this cell

24:28 Deletion of the Maximum Element

25:00 so we want to get rid of the 87 now of course that's not a good state to be in because now we don't really have a valid heap so again we have to do something

25:19 but let me write this down finding the max is easy but when we remove it so we have to do something about this and the only thing we can really do is change the shape of the tree again in the only way that's that's allowed and that means taking out this element

26:02 so that's what we'll do the 25 moves up here this becomes empty and this is gone so we're almost good the heap shape the the tree shape is fine

26:18 but the heap property the heap order is violated so we have to do something about this we have to fix it again and how do we do this well um

26:35 there's only really uh one thing we can do we have to let this down let this element sink down to find a proper place in the heap uh that's the the term that's usually used

27:02 now uh probably need a little more space so how can we do this the problem here is that we have two violations it's violated here and here but we can only put the 25 down into one of the two slots now which one should we take um if we would swap the 25 with the 66 the 66 would still violate the heap condition with the 70. so we can't do this instead we have to compare these two children with each other and we take the bigger one so that's the bigger child so that's the one that we swap so let's uh actually do this maybe we don't need the the red circle anymore here we put the 70 up here and we put the 25 down there now by picking the larger child we make sure that this is fine and so the whole subtree here is fine and we made sure this is fine but we still have a violation here

28:24 and so that you can follow this in this in the lecture notes i'll i'll just keep that here so we swap those two again i use blue for the swap so that's the bigger child in this case so we take that one swap it with this one and then you're left with

28:53 and the 25 and now we have uh restored the heap property and that's uh how you delete the maximum in a heap again any questions let me know um i know i'm pacing fairly fast through this but i think if you understand this on the example you should be able to figure out how this works in general and be able to implement it if necessary but yeah as i said the the videos show this in much more detail and the textbook also has has code for this

29:33 the last operation i want to discuss is how to construct a heap when we start with a given set of elements and well we could do n times insert

29:51 but you would if you analyze this the total time would be n log n overall time you have to be a little careful because uh the insertion takes time log of k for the current size of the heap and the heap initially is small but if you look at the last half of the elements then the heap has already sized at least n half and that's enough to establish the n log n

30:23 but we can do better than the n log n and the idea is to start with small heaps and merge them so you first start uh let's take our um

30:38 i probably don't have time to go through the full worked example so you take the last half of your elements and put them as individual numbers here then you take the next quarter of your elements and put them above these sorry that's uh this should be here and you make these little heaps of size three what you have to do that for that is let is let each of these sink down

31:19 all right after you've done that you have these um little heaps and each of these is a each of these is a nice little heap um let me indicate that with the

31:55 so what i mean by that each is a is a true heap in that it has the right shape and it satisfies the heap order now you put the next elements up here and do the same thing you connect this these two heaps pair them up and again you do a sink for the root and you do this one more time and then you have uh the entire heap

32:27 and now why why is this more efficient you need roughly a quarter times sink in and the next step step you would need for an eighth of the note sink in a heap of size uh seven and so on this is always a power of two minus one at most the last one could be smaller and here you divide by n to the two to the k now if you sum this all up you will stop when k is log n and so summing these all up because most of the insertions of elements are in small heaps the total cost is is linear for this heap construction if you do this bottom up merging of heaps together

33:39 so uh let me just write that down and um that only leaves to to wrap up the um binary heaps i will i will prepare that for next time so let me save a little time on that

34:12 that concludes the construction of heaps and that concludes the three basic operations of a priority queue and how you can do them on binary heaps you can similarly do the change key operations by letting a node sink up and down depending on how the node depending on how the weight has changed and you can do similarly the other operations um but what i've shown you gives you the the core picture um and that's that's how we use that um i'll i'll give the overview slides next time to save time on that