Video 2-3: §2.3 Priority queues & binary heaps

0:03 in the next section we'll look at a more interesting absor data type the priority cues and how to implement it and uh again because many of you have seen this I want to start with just this question checking what you uh know about this already now if you haven't seen binary heaps there's no way you can know the question so you can just put in some random guess uh it doesn't really matter

0:34 uh the other point if if you have seen it um read very careful uh the different answers so it's just asking about Heap ordered um I want to give some some of people a chance to vote and I'll briefly show you again what the what the tally in the room looks like uh I won't discuss it then because basically the rest of this section will answer that

1:31 question uh so let me show things at this point um most people say it's a tree where all keys in the left sub tree are smaller than the key of the root and all keys in the right sub tree are bigger than the key at the root and uh yeah you'll you'll see uh you'll see about that right but let's before we talk about heaps that will be the implementation the data structure let's first talk about the abstract data type the interface and that's uh called the priority q h i put this like a put this glass in a plane in there because sometimes you get people that have priority boarding or priority security and they can just uh skip the queue right that's the uh rough idea of a priority queue uh but it's a little more less binary there's if you board the plane you're either standard economy or priority or business class or whatever uh here it's not not so uh strict um with just two priorities uh instead we have a a way to insert elements where we specify a number or some other order thing that tells its priority so it's a whole Spectrum um and then you can at each point in time ask for the element with the maximal

2:49 priority or you can delete that element and these two operations will try to do quick as well as insert um sometimes we'll also also need a change key operation where uh you can update the priority of something to a new priority uh we'll we'll only talk briefly about this um but insert and delete Maxs are the the main operations for priority cues now this is all formulated where the maximal element is what we'll remove and I'll I'll try to be um consistent in using the max oriented version because that is what is used in the red book the algorithms book that I gave you as a resource for this unit uh but there is a symmetric version where everything where I say Max is replaced by Min and it's just the same thing um and some books rather use Min it depends on what application you have in mind what is more natural so just keep that in mind both exists and both make sense uh they're just symmetric

4:00 versions all right let's again briefly check that the definition is clear so here's um a bunch of numbers that are inserted into a priority Q come on and then you call delete

5:00 question all right um we have a clear majority and uh you can still put your vote in uh what's supposed to happen in a priority cue is that the element with the largest priority gets removed first if you call delete Max uh what I didn't say in this question uh and what what we'll also do in the slides is when I insert numbers uh I'll just treat the number as its own priority so the number the value and the priority are the same you will see that um for so in this case we should remove nine because that's the biggest number that's that's what I meant by not a trick question uh it might have been slightly tricky as a question because I said insert needs to have two parameters a value and a priority associated with it for all of the slides we'll just assume that X is not important it's actually never interesting for the implementation you just carry that along and the priority is all we care about and we'll just use numbers uh as of an abbreviation but the implementations can be more

6:13 General we have an abstract data type so uh we can think about implementations for that abstract data type and again there's many options and before you start with something complicated you should check that the simple versions don't really uh cut it there's usually two obvious Solutions you can either have an unorder list so you just keep the elements when they are inserted you put them at the back uh so that's very fast for insert but then you have no idea how to find the maximum now you can be slightly more clever you can try to keep track of the maximum but then if you remove that maximum you don't know how to find the next smallest and so on this is is not really uh leading anywhere so the delete Max will always be slow in this the other option is you uh keep the elements in sorted order somehow and we'll we'll talk more about this um but if you keep that if you keep that in a list you don't really have a way to jump to the right position to insert a new element so suppose you have those elements all in a link list or in an array it doesn't matter for that for that fact now you know the new element

7:18 should go in the middle there's no way for you to get there so it's all not really useful here seems sorted doesn't help uh if you think about it these are two extremes entirely unsorted or fully sorted and maybe uh it's it's more useful to have something in between a slightly sorted list and that's exactly what we'll what we'll use um so forget about the picture in the top for the moment if you've seen binary heaps before you may have seen different versions so maybe I also try to forget that for a second uh binary heaps can be defined either as um arrays or as trees let's first look at the array view so you have uh an array with the following weird property for every position you know that its value is is smaller than if you take half of that index and that is something like a slightly sorted list right it just means for for every element there's one other if I take an element here there's one at half the index which is which is bigger it's a slightly weird condition um but if you think about it you can you can reason from that that the maximum has to be in the first position and so on a much more natural way to think

8:41 about that is to imagine a binary tree behind this and that's what we'll what we'll use for thinking about the operations uh but what makes binary heaps um what makes binary heaps so fast is that they can be implemented in just an array by using index uh index computations but the tree is the one that's more Illuminating so a binary Heap is a tree that has two properties first of all it has a specific shape it's a complete binary tree uh and it's Heap ordered and to get the terms there at least mentioned uh a binary tree in general is a tree where we have nodes we have a single root somewhere at the top computer scientists so weird right we have one roote and that's at the top uh yeah uh and you have two children for each node a left child and a right child no political implications um and either one can be missing they can be empty or null uh and then you can form larger trees from this uh as you wish and they can have any shape a binary tree just says every node has a pointer for a left child a pointer for a right child and either of them can be empty so that's one example a complete

10:08 binary tree is one that has a very specific shape namely it always has um all nodes filled so all children exist except for this last uh level here where there's a a a part on the left where all children exist and then the rest there's no children so I I'll just draw this with this with this fat line to indicate it if you want to be more formal then everything up to the penultimate level is complete so every note has exactly two children and on the on the penultimate level from the left there should be children in all cases and then no children

10:49 afterwards the second thing we have to talk about is Heap order and that's essentially what this encodes um but in the tree it's much more natural a heap order just means this uh for every note the parent is larger than the children

11:10 okay now um why is that why is it true that these two fuse are the same and why is it that we can think about trees when we store things in an array and vice versa uh that's because if we have this nice shape of a complete binary tree we can uh store the nodes in an

11:37 array in what what we call level order so we start with this Noe then we go down to the next level then we do these two then these two and then these two you walk along the green line and assign indices to the array just in increasing order so that one will be stored um at position zero or one

12:00 yeah um I want to stay consistent with the book I think they start at at one in this case just to make the math a little nicer and then these two three four five 6 7 8 9

12:22 10 again something for you to work out at home if you if you want um this condition on an array corresponds to that condition about parents and child and children if you store the notes in this way in an array in level

12:46 order is there a typical nice interview question that people ask in technical interviews you're given a binary tree with pointers Traverse it in level order uh but I'm not going to do that with you now here's an example that I prepared uh of a binary Heap with concrete numbers as values and so you see when whenever you walk down a path from the root to some Leaf in the tree you see the numbers going down okay 87 is bigger than 66 bigger than 40 bigger than 25 now between different siblings or uh between different nodes on the same level there's no order enforced so only if you go down the tree there's an ordering but this is enough to guarantee that the maximum has to be in the root if it was anywhere else it would have violated the condition with its parent the only node in a tree that doesn't have a parent is the root so the maximum is always there which means the operation of finding the maximum is really easy and we'll talk we'll look at the other operations in a second and I'll keep a copy of this because we'll want to uh want to work with that

14:04 let me motivate a little bit why we do this and then I'll show you how it's done but uh I think it's it's insightful if you see this first the definition why this weird shape of the tree and why this weird uh invariant it's maybe not so obvious um the shape of this complete binary tree just makes things a bit more simple because for every size there's exactly one way the tree can look right you think about it's completely defined it has to be complete up to a certain point and all the children up to a certain point have to exist so the shape is is

14:40 unique this shape also has the nice property that it has minimal height among all trees with that number of notes there's some others with the same height but it's among those with minimal height and the last part is the most important because it has this very nice regular shape it's a very easy if you store it in an array in level order to navigate between the nodes and you can work this out and the videos I linked on the website do this in much more detail for now let's just take it for for granted you can go to the left child right child or parent by just doing Simple arithmetic on the um on the index and that's all we need so yeah this um this use is

15:30 that we start the array at index one you can just use a standard array with starting at zero and leave the first one empty but it makes the math a little nicer if you start at one waste this one memory

15:46 cell the second part I already alluded to why why inforce Heap order well that means the root is the maximum and uh on the other side only this paths down from the root are sorted so you don't sort too much because if you sort too much you get trouble in with insertions to figure out where exactly things can go but how to do inserts um we still have to talk

16:14 about so as you will have seen now for the question from before that's the right answer Heap ordered just to repeat it means at every note your value is smaller than your parent unless you have no parent then it doesn't matter