Video 3-4: Priority Queues and Binary Heaps

0:03 In the next section, we'll recap priority cues and binary heaps as one of the other fundamental data structures that algorithms build on and use.

0:12 And let me um put that to a test of what people remember about these. What is a heap ordered tree? Four little um options. Again, not something I've told you. This is rather to check whether we should revisit this in a bit more detail or not.

1:41 Okay, we had nine votes earlier for the introduction question. So maybe let me show you the votes. Let me lock this for now. Uh so maybe let's revisit this briefly. Um I put this on purpose because the other answers are also well-known data structures and uh it's kind of a traditional thing that you mix those up. Um it takes me one or two slides to come back to this. Uh first of all, let's discuss the abstract data type. What is this? What is the outside interface we're looking at here? And that's the notion of a priority queue. Uh I put this picture here because somehow priority queue for me is like priority boarding and someone's sitting on the plane with a nice drink. That's somehow higher priority. Maybe you keep that in mind. Um otherwise not endorsing alcohol in the lecture. So the operations I can construct them from some given elements. The interesting ones are I can insert a new object with um a given priority. So we distinguish between the the object itself and its priority.

2:51 Um the priority could be some number but it could in general be just anything that we can compare. Um we'll see some examples also later in the module. Then I can also ask I can always ask what's the largest priority item in my current Q and I can remove that one. And the idea is that delete max returns that maximum priority item. So think of this as how you would want to organize your to-do list, right? There's a way if someone tells you you need to do this and that. You say, "Okay, insert. I'm I'm going to do that eventually. I'm writing it down now so I can clear my head." And I give it a priority because, you know, some things are a bit more important or urgent than others. And if you wake up in the morning, you say, "Delete max. That's my first thing for today." And then you hopefully get through many delete maxes on that day. Now, sometimes you also need this prop this uh operation that somebody comes along and you know this favor I asked you last week about is really urgent now. Please, please, please. And then maybe you have an item already in your to-do list that now gets bumped up to a higher priority. [snorts] Uh that's that's all. Now, for some applications, this maximum formulation is less natural. So there's also a cousin, the symmetric cousin is the minor oriented priority Q where all max is replaced by min.

4:19 We'll usually just do an implementation for one and then you can essentially reverse everything to get the other. Uh that's no big deal, but depending on which book you read, they might either talk about delete min or about delete max. So you have to kind of be aware that the terminology is is not uniform there.

4:43 Let's look at some very stupid implementations of this before we get to the the proper ones. You could just keep things in an unordered list. When you add some when you insert something new, you just append it at the end. Um, so that's cheap. On the other hand, there's no structure. So if you want to find the minimum or delete the uh maximum maximum oriented if you want to delete the maximum you just have to go through all the elements and find it. Uh you could also try to keep a sorted list instead. So then uh finding the maximum is easy. It's always on say the first position. But now insert became rather expensive. And you might say okay if that's a sorted list I can binary search right and you're we'll come to that. But the insertion itself somehow then if it's an array you need to move things or if it's not an array how do you do binary search? So there's a there's a problem there. If you stay with some simple linked list implementations or arrays then you're stuck with insert taking linear time. So that's also not good, right? Your friend's waiting for your answer whether you can do that favor and you're still looking through your list to insert the the new task. So what we seem to want here is neither completely unsorted nor completely sorted. Something in the middle. Okay. And that something in the middle indeed exists. It's called a heap.

6:08 That's the way to think about it in my view. Um this slightly sorted list is kind of this array few which is this very awkward definition. If you forget about this for the moment and focus on this, it says for every position, the entry in the array is smaller than the position at half the index. What another idea, right? This is sounds completely useless. Now if you think about it, it it kind of means that the maximum has to be uh in the first position because if it was anywhere else, it would contradict this definition with its position and the position half there's always something to the left and that has to be even bigger. So the maximum has to be in position one.

7:10 Okay. Uh here in deviation from the usual uh indexing in the module we start at one precisely because it makes the calculation that we use here more convenient. Just think of array index zero being left unused.

7:27 This is a very clever definition that makes the maximum appear in the first position and it turns out you can maintain this efficiently. But to understand why this is completely crazy, you really want to view it instead as a tree. And that's I think is easiest seen in an example. So um let me move here. Uh here's some example heap. The official heap is just this array, right? That's the partly sorted list. And you note the maximum is indeed here in the first position. And if you take any other one uh the numbers are rather small. So this is index 14. This uh 68 and what's highlighted here is uh index 7 half the index or for 13 let's say 15 is always the index half and then rounded down. So 15 half rounded down is also seven. And you see that 41 and 68 are both smaller than 82 the index the um element in index 7.

8:39 So this satisfies this heap property. Now uh on top of that is the tree you should think of which is the first element is in the root. Then the next level the two here on this level are the next two elements in the array two and three. And then come these four and then these and then these. That's the order in the array which you can see much more clearly if you um move this around to align with the array. Now the elements are in the tree in the order they are in the array. Now the tree is not so visible anymore but it is the same tree. Okay.

9:24 So what is true in this tree though is that every element is larger than its two children. That is precisely what this heap conditioning codes because the this you have to work out if you um if you start in in this few um at any element its parent is at index it's index half rounded down. So from 10 I go to five. And you can prove this inductively that this is always true. It has to do with the fact that the um the number of elements on the level is always a power of two and summing up the previous powers of two plus uh gets you to the next power of 2 minus one. Okay. So if at every position I'm larger than my two children, then clearly the maximum must be in the root. That's what we figured out before. And this also means um I'm very constrained on the operations of what has to happen.

10:44 So um briefly back to the slides uh here's an example again to um fix that notation is the mapping between array and tree clear now and the heap now coming back to this uh this question from before um a heap ordered tree is precisely this every node is larger than its two children.

11:18 Now, why do we like these shapes of trees? Why is that the right notion of of being partially ordered? First of all, it's very simple. There's only a single shape for the tree that's allowed. namely all levels full and then flush left on the last level. There's a single tree for every number n of of nodes. And so I always know what shape I'm supposed to have. Also among all trees with the same number of nodes, this kind of shape of tree almost perfectly balanced or almost complete has the minimal height. And so to be be specific here, let's let's fix the definition there. Let's uh draw some some actual tree here.

12:22 That might be our heap. And then we have these levels that the nodes lie on. Then um the height of this tree is the largest distance from the root to any of the leaves counted in edges.

12:54 So whenever I have to go one level down that is a plus one in height and I get that as as three for this example. And you can prove for all trees that store nodes in total, this shape is among the trees with the smallest height.

13:10 Uh the more crucial part for for operations on these heaps is this last step. This shape because it's so structured and so constrained, it gives you direct access from a node to its parent and its children. I've shown you on the example already. This was precisely from the heap definition that's going to the parent. And then the left and right child of a certain node at index k is just doubling the index and doubling the index plus one. And this works so nicely if you start counting at one for the indices. That's why we do that here.

13:52 Uh the second part of the definition of a heap is this heap ordered property and that's obviously to make extract to make finding the maximum easy and fast.

14:07 Note that um so we're sorted along any path from the root downwards. There we always have this is larger, this is larger, this is larger, but there's no ordering among the leaves.

14:20 These could all be in a completely arbitrary order. So overall we're imposing rather little structure on the keys in such a heap on the arrangement of the values. That's what again makes makes it possible to have fast operations.