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

0:00 <Untitled Chapter 1>

0:04 all right in the next section i want to talk about a more interesting data type both the both the abstract data type and the implementation is a little more interesting than what we talked about before and these are priority queues respectively binary heaps

0:24 so let's have a quick look on on slido if you already know what heaps are i know that quite a few people said they haven't seen it in which case you will

0:39 maybe we can get a few more answers in five four three two one and locked all right uh there's your answer and well i can reveal it at this point but uh no didn't i want to unlock

1:30 this might reflect that you were thinking of binary search trees the way i ask this question and put this mean answer in is because people often confuse the two so you're not alone we'll talk about what binary tree heaps are in a second but first the abstract data type

1:53 you can't see that one all right i've got my mouse for today so i pull it back and forth all the time before we talk about binary heaps the abstract data type is called a priority queue and i put this this seed in if you ever get a free upgrade maybe you get to skip in the boarding the other queue where the plebs has to wait and you can just walk past because you've been assigned higher priority uh that's roughly what a priority queue also uh allows in a more structured way but uh it's maybe a bit more socially acceptable so what is a priority queue it's an abstract data type so it's defined by operations you can construct one from a given set of elements you can insert something and now you you don't just insert some element x but you specify a priority for this element think of this as just any number it doesn't have to be a fixed set of categories can be can be any anything you can compare

3:06 and then the priority queue allows you to get quick access to the element with the maximal priority and also allows you to remove that one and sometimes it allows you to change the priority q the priority of an existing element that's already in the queue

3:28 all right and you can check if it's empty it's a building block for many algorithms uh again i think a key success of computer science was this abstraction of finding as an as an abstract block that you can use this notion of a priority queue uh that led to many developments maybe i'll touch on this later a bit more

3:55 there's always two versions of priority queue depending on the application one or the other is more natural i said everything about maxima but you can take minimum instead of course you can negate the priorities then you also get this so these these are the same i'm using the max oriented version in in this unit because this is how the the book i recommended or the videos and the book i recommend it is formulated but both works

4:20 Clicker Question

4:23 uh let's have a quick test if you if this definition is clear to you if i could find the question that would help you can think about it and i'll try to find the question

5:30 so what i mean here by by these numbers is the numbers are the elements and the priority itself they are the same in this case that's what you often do if you just discuss the

5:58 all right uh many people have voted and it seems quite clear so let me lock it in three two one [Music] all right okay that works well done um

6:25 so the idea is you remove the smallest element right that's uh that's not so not so hard but the thing is it doesn't depend in which order you insert elements

6:37 PQ implementations Elementary implementaties

6:38 okay you can do very simple things so the abstract data type tells you what you should do and there's easy ways to do that if you're willing to have a slow implementation uh for example you can just store all the elements that you insert that you insert into a list um so the list here can be the python list in that sense uh doesn't matter how it's implemented really then you can append in constant time or constant amortized time but to find the minimum or maximum you have to walk through the list and compare everything you can do the opposite you can keep everything completely sorted that's great because you can find the the smallest element right at the front or the largest right at the back but if you want to insert uh it's not so clear how to do this if it's an array you would have to copy things over and you have to find the insertion position

7:42 but these are easy ways how you can do it and what we'll discuss next is something that's trying to come to be between those two extremes a completely unordered list is slow for finding a minimum completely sorted is slow for inserting can we have something like a slightly sorted list and this is what binary heaps effectively are and they also have the the needs additional property that new elements are added at the end so you can use again tricks like resizable arrays to get that in constant amortized time now uh

8:26 i don't want to spend much time on this heaps are essentially trees for me you can store them in an array because they happen to have a specific shape

8:48 but let me illustrate this here just in a in a simple example what i mean by a level order so we'll we'll work with the tree view for the rest of this unit so we'll just think of nodes and they can have two children a left child and a right child and they can have a parent um and so we'll have properties about this um i'll come to that in a second that's that's important for this mapping but we you can actually store the elements not in a in a tree where say you represent each node as an as an object with two pointers to its children and maybe another pointer to the parent instead you can store them just in one plane array by listing the notes in level order so you walk first the root then the children of the root then the grandchildren of the root and so on always left to right okay that's called level order

9:01 PQ implementations Elementary implementations

9:56 and there's a neat way if you have a note you can go to its two children or its parent in a heap by just doing arithmetic with the index if you take i and multiply it with 2 and multiply 2 plus 1 you get to the children that's because the heaps have a specific shape so for this for this unit we'll ignore the array view but this it's worth for you it's worth knowing that this is possible because that's what makes heaps very efficient you can use a contiguous piece of memory to store the nodes you don't need pointers but what we'll think of is in terms of the tree now what is a heap what's a binary heap it is a tree with two properties first it's a complete binary tree which means it looks something like this tree up here but slightly more generally it can have more children at the next level but it will always have all the children flush left as far to the left as possible and apart from the last level all the other levels have to be completely full okay so every every node has exactly two children except when it is on the penultimate level there might be some that have no children and there might be one node

11:16 that has only a left child i have another example on the next slide the second property is what the slider question was asking for it is heap ordered where um the the key in the pair in every parent node is bigger than any key in the child nodes

11:41 Binary heap example

11:44 let's see uh an example that i prepared that's a binary heap with uh just numbers for the keys it has the shape that we want because every node has exactly two children except well some on the on the second to last level and uh at every node it's true that its key its number is bigger than both of its children okay that's a binary heap clear

12:15 well you can't always you can't always do that uh if this is like uh uh that has 10 keys i guess there's no way to have a tree with ten notes without having one note having only one child or several having only one child just doesn't work out if you think about it so uh it's it's inevitable that the 40 has a single child but this is the only sold exception every other node either has no children because it's here on this on this last level uh or it has exactly two okay

13:01 now you might wonder why do we like this weird kind of tree uh one good thing about it is even though it's a binary tree there's only really one shape of these of these binary heaps for every size because it's completely determined you have to fill up all the levels except for the last and the last one is everything as far to the left as possible so there's no no choice and that makes it simple so that's good also

13:36 this simplicity means that you can map from indices to uh from the nodes to index indices in an array in an easy way it's also good because the height of this tree is minimal among all binary trees that's something we'll come back to and you can navigate so this is how you navigate the indices i think i already said this and we don't really need it in the future so that explains why we want this this weird shape the complete binary tree shape why might we want the heap order if you think about it as an array uh that's again sorry for the flipping uh here it is formulated what what is true on the array for every index um basically uh the position i is smaller than half its index so it is somehow sorted with the smallest with this with the big element to the left and the smaller elements to the right but it's not exactly sorted it only says if i'm here at position i then i'm bigger than what's i'm sorry i'm smaller than what's at half my index so this is exactly this slightly sorted and this turns out to be exactly the right notion for this all right the tree the tree on the on the tree shape it's

15:07 easy to see that the root is the maximum maybe this is in the example it's obvious because the root has to be bigger than all its children in in key and those also have to be bigger than all their children so if there was any other element bigger than the root that would be a violation so the root has the maximal key and that's one of the operations we wanted so that's good

15:36 and along the paths of the tree things are in order so again i drew one path here if you follow any path from the root down the tree you always see an decreasing sorted list okay so that's this slightly sorted in yet another term

16:01 and i think we'll i'll have to finish today with this cliffhanger so it's a slightly sorted list it seems good because we can find the maximum what i haven't shown you today is how you can maintain this remember priority queues want to allow these operations of removing the maximal element adding new elements and maybe even changing keys and we'll have to make sure that these operations don't break these invariants they want to take one binary tree one binary heap and create a new binary heap and we'll we'll see next time how this works