Video 3-1: Recap: Priority Queues and Binary Heaps

0:03 In the next unit, we'll look at a kind of fresh topic. You'll see there's a connection to the previous one. Um, but now we're looking at a more restricted abstract data type, priority cues.

0:14 Um, I have a few that I want to um mention. Um, we'll do a bit of a a recap and ease you into thinking in terms of tournament trees instead of binary heaps. um then you'll see lazy search trees again in a special case where it's it's so much cleaner and simpler. You'll see. Uh I want to say a few things about Fibonacci heaps but not do the full proofs because I find them rather unpleasant uh and instead present you some some alternative which uh achieves the same uh in terms of complexities with a much cleaner um analysis.

1:01 Let me remind you what a priority Q is just in case uh you forgot. Um everything here will be minor oriented. So I have an operation for removing the minimum and that's the only kind of destructive operation or query operation that I have. I can only find the element with the smallest priority that was at some point inserted. I'm formally distinguishing between the element that we insert and its priority. Uh for the data structure, it will not make a big difference. Um maybe I'm sometimes just saying priority is the entire object. You know how to represent this in object- oriented ways. Um that's not the big deal. So uh you can construct a priority queue from some given set of elements which often is more um efficient than doing inserts repeated. That's at least true for binary uh binary heaps. Uh the aim will be to make insert so fast that it doesn't make a difference but fine you can still keep this operation. Um then the other important operation is decrease key. an item that's already in the heap, you might make even more urgent than it already is. So be extracted even even earlier than you originally planned, but not the other way around. You cannot postpone the deletion of an element in the same way. Um again for binary heaps, these two options are symmetric and uh wouldn't affect the running time, but in general they do.

2:34 Um the last one is uh is not as often needed um in the simple applications of priority cues. Um but still uh uh you can support this this melt operation which is a bit like like a join for binary search trees but it's got a different name for a reason because it makes no assumptions about the keys or the priorities in these Q two priority cues. They can be arbitrary.

3:07 Of course this is because they're not sorted and so life is a bit easier. Okay. Um at this point maybe let me go back to the question. So um people have seen binary heaps and quick heaps which is cool. Uh we'll come come briefly to that um in the LP heaps part. Uh but don't don't worry if you haven't seen all of those. uh binary heaps is the classic example that uh undergrad data structure courses include and they can do these operations in these times. I've included melt but this is essentially rebuilt from scratch. Binary heaps cannot really do melt in any sensible way and you can even think about that the way they are structured there's no way to do it much better. uh at least you have to move a lot of data around but at least they get um the key operations in logarithmic time. Not bad. On the other hand, always find this unsatisfying that by and large you can get the very same complexities with the standard binary search tree without thinking uh if you just use it as a priority queue.

4:22 There's one exception uh which is the construction from a given set of elements. That's linear time for a binary heap. But it can't be because of sorting for a binary search tree. You could uh now that you're primed thinking about lazy search trees, you will of course maybe know other options, but we'll come back to that. So maybe there's not so much point in having heaps. Well, yes, there is because uh binary heaps are not the end of the game. uh there's different structures and we'll see several of them that can improve the complexities of all operations but delete max delete min um again the reason in general is you cannot have all these operations faster than login time because of heapsort. You can take a priority queue, insert n elements, get them out in sorted order.

5:21 So that process in total has to cost n login time or comparisons. And um maybe you can make some of these operations faster, but then at the expense of another. You can't all have them sub logarithmic.

5:39 And the typical choice is that delete min is logarithmic and the other is maybe even constant. Uh in the remaining quick time let me remind you of um binary heaps which you've seen. Uh what I've shown here is the shape of a classical binary binary heap. But the values in there well I guess this also heap ordered. So it could be what I meant is that these are array indices. The cool thing about binary heaps and their rigid shape which is uh almost complete full binary tree, right? So uh all the leaves are on two consecutive levels and the full the the lower level is flush left. So they always have this this kind of shape. Okay, let me draw it a bit nicer.

6:40 They always look like this in some way or another. Uh this has the nice nice property that you can do uh a level order traversal where you go uh let me try even nicer now we're messing anyways. So you go through this level by level. That's the order in which you visit these notes.

7:29 I don't know if that's much clearer. Okay. Uh you can enumerate the vertices the nodes of the tree in level order and then you get the indices the the well you get the order in which they appear in an array. And that has the nice feature if you draw it slightly differently. It's the same tree just stretched that to get from some vertex to its two children. Just take the index and multiply it by two. So now you go to 18 at 19. These are the two children which in my drawing you can maybe make out maybe you can see it for four that it has eight and nine as the children. That's the magic of the rigid shape that it allows you to do that and efficiently do that.

8:18 Um and pictographically let me just remind people how the operations were done uh without explaining them in more detail. How do you do um extract min Well, the minimum in a minor oriented tree is always at the root. So, you delete this.

8:53 Okay, I got the minimum. But now I messed up my heap shape. I can't leave it where where that is. So, I'll have to take the last element previously in the heap and move it to the root into the root. That's fine. Now the shape is again what it's supposed to be but I might have messed up the heap property. So there's a third step where now the one smaller heap you uh swap the element successively with its larger child smaller child. And so uh it sinks down in the heap step by step until it either reaches the leaf level as in my drawing or it may also stop in between if both children are larger than the element. So that was uh remove the root Um also note that this last step so these these two are essentially for free in comparison world. Uh how many comparisons does this last step take of login? But can we say it more precisely at the worst case if it has to go say to the leaf level >> that's right has to do with the height because this is a a a perfectly balanced binary tree. The height is going to be log n maybe + one.

10:54 Uh I don't I don't care about the plus one. That's not what I'm getting at. Um but a fun observation is that it's two times that uh well okay let me let me say with some uh error term and the factor two comes from I first have to check which of my children is smaller and then I have to check whether I am smaller than that child and these are two comparisons per level. That's also why heap sort is kind of worse than merge sort in terms of comparisons because it has to do this this sync down step n times. Okay. uh insert, you just put a new element here. And now instead of sink down, you uh swim up new element and it rises often times probably not that much, but that depends on the elements. Uh funnily here, it's only one comparison per level because there's a single parent. It's a certain asymmetry.

12:24 what I wanted to briefly say is that you can also change the priority of any element in the heap. And depending whether it's now smaller or larger, it either swims a bit further up or it sinks further down. But it doesn't matter much. The factor in front of the login may change. Same as before. Uh but you can do both operations in roughly the same cost at most the height of the uh of the heap.

12:59 Um and then you can update the priority of any element if if you know where to find it in the heap. So you need all of these operations assume that there is some some pointer to this element x. Uh so insert gives you some handle to this element which later you can pass to decrease key to change the key. Some sort of such a a handle is needed. Okay that's binary heaps. Um, and then new stuff next time.