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

0:00 <Untitled Chapter 1>

0:04 in this next section on fundamental data structures we'll look at priority queues that's the abstract data type and the implementation that's most most well known and uh say most most befitted for the fundamental data structures uh Topic at least binary heaps

0:25 before we start let's see this is basically just checking uh what you've had about this before thank you so you're not really supposed to know this already from what I told you but you might know this from undergraduate classes so without much further comments um I'll leave that question open

1:07 well 47 people made it for the attendance code yet but there's a few people coming late I'll show the attendance code later again uh so we should I think we should aim for at least 50 answers on that one

1:23 um I should give you a fair chance to read the question and put in your answers but it's independent of the next slide so most most people seem to be looking at me all the slides are both uh so let's let's um introduce the key abstract data type of this section and that's called a priority queue I put this funny you know this is supposed to be first class in your airline so one of the perks of flying first class uh not that I've ever done it but uh I heard it exists is that you get priority boarding so there's a queue when you line up for boarding the plane and if you're Ordinary People Like Us with a cheap ticket you have to line up in a queue as we've seen it last week but if you bought in a higher priority then you can skip the queue and go in first independent of the insertion order in the back of people at the at the terminal or at the at the gate so a priority queue is is kind of capturing this and I hope that this picture sticks in mind um better than anything I could I could draw uh the formal operations are like this um we'll we'll also have the operation to

1:44 Priority Queue

2:41 start with an empty priority queue but we'll generalize this a little bit here's uh an operation that takes a given array or list of of items and constructs a priority queue from that we'll focus on on when it's given us an array because that's most convenient for for binary heaps at least the the most important operations are insert and delete Max so insert inserts a new element into this priority queue into this bag and we're giving two two different pieces of information the element itself X and some number or or at least some some element from a an ordered Universe a priority p and so when you ask for an element in the queue all you can do is really get the one with the highest priority that's why this function is called delete Max it gives you back whatever element currently is in the queue that has the largest P all right there's a few other things you can peek at what is currently the one with the largest priority and there's some there's a way to change priorities of the things that are currently inside the priority queue foreign sometimes we can also support a delete operation I left that out here because it doesn't add much to our story and you can check if it's if it's empty

4:11 priority queues are a convenient building block uh whenever you have to deal with things that arrive out of order but you want them in some in some sorted order but it's a dynamic process you can't just wait for all the elements to arrive and sort them you want to be able to insert them and get some out intermixed foreign

4:49 uh I don't really want to show you the results right now will overcome or you will discover what the right answer is later anyways uh let me instead switch back to the attendance code before we need another question

5:13 foreign the way I formulated the priority qadt here is the way that our key Source this this textbook the the red textbook algorithms uh by Centric in Wayne formulates the problem where you can delete the maximum element you can you can also have a symmetric version where everything's flipped so instead of the maximum you get the minimum uh the rest is all the same now uh a priority queue can always just do one thing it can either get you always the maximum or it always gets you the minimum we don't at this point consider that you can mix these two operations

5:58 so I just listed this here in detail because many many other textbooks prefer the minoriented version but if you have an implementation of one you could you could think of just negating the priorities and then you get the other there's usually simple tricks to go from from one to the other okay

6:20 so let's see if the definition of the priority queue is clear to everyone it's not a trick question it's not not anything really uh spectacular oh cool you might you might be able to get by with mobile because at least this room is at the edge of the building uh I mean I told you why I'm not live streaming over at your room

7:45 okay I'll uh if it doesn't come back maybe we'll just take this take this question out of the participation I'll have seen that you logged in earlier and did you have the issue before for the previous question where it just died out now all right uh let's pretend you you all answered nine in this case uh most of you did so the thing is it doesn't matter for a priority queue in what order you insert the elements the only thing that matters is the value if I write it like here that we just say insert these numbers then the meaning is that the the item X and the priority p is just the same thing that's often a simplification if you want for the for the syntax if the element itself is is ordered there's a number you can say the element and its priority are are uh the same thing that's what was meant in this case

8:56 okay so we defined an abstract data type that is our wish list what we would like to be able to do now we should also think about how to realize that um and before we start with something more sophisticated let's think about how far can we go with just the very simplest ideas I think it's it's usually uh it doesn't take more than a few minutes to come up with these two ideas you can either have the elements in some random order maybe you keep them just in insertion order then insert is really cheap you could for example use a resizable array from last week or a linked list would also do but if you want to find the maximum there's nothing to get to help you really to speed up that process so you have to go through all the elements and find the maximum and uh to be clear linear time for the operations here is is not interesting you could just do that uh without any data structuring assorted list seems more promising where after all we're trying to get the maximum right which is uh we can at least find the maximum very easily in constant time if it's a say a doubly linked list we could also remove it in

10:07 constant time but now insertion is has become more tricky because at least if it's a linked list it's not clear how to put the element at its proper position without walking through the list so both of these are not really a satisfactory but they're easy to program it's one thing so we'd like to get something in between this had very fast insert it's had very fast delete Max but the two other operations were really slow can we get something that's in between in a way what we want is a slightly sorted list it should be sorted enough to get the maximum fast but not so sordid that it takes H's to insert that sounds a bit weird right uh but that's exactly what a binary Heap is if you look at it from the right the right way it's it's really a slightly sorted list or slightly sorted array the confusion often arises that people talk about binary heaps and mean two different things they are equivalent in a way uh that I'll I'll talk about in a second but you usually see one or these two descriptions first and if you've seen one but not the other and someone talks about the other and not the one you're confused so I'll try to start by showing both

11:26 pardon um okay let's let's maybe take that offline um so if if you look at the Heap you have an array and you require instead of sorted where you would say every element is smaller is bigger say it's the other way around we want the maximum uh completely sorted would be at every position the element is bigger than the one right to it now here we say something weaker we say uh every element further behind is smaller than half of its position right sounds like a completely weird and useless definition but that's one way to define a heap in the array notation and the other is a heap ordered binary tree and we'll we'll come to that in a second

12:37 um I think that's the point where we want to talk about binary trees right that hasn't occurred yet so there's a few things um that popped up in this that some of you may know and others may not the first is the notion of a of a binary tree a binary tree is any kind of order Tree in in mathematical syntax where we have notes and they can have two children they have a left and a right child and both can be empty a null pointer if you want I think it's most natural to imagine that these are objects and they have two fields which are Pointers they have a left and a right pointer and so every element can have another two children or it may not have one and it could also have just a single child as in this case and then the left pointer would just be and would just be null

13:40 now people often don't don't draw the null pointers uh just to be a bit more concise in the drawing so that's that's a binary tree definition is every node has two potential children a left and a right one both could be null or some other binary tree node and we don't allow Loops so if if someone is pointing downwards you have to follow there's no way that this guy's child is is one of the ancestors that's not allowed

14:17 no weird family constructions um now uh a complete binary tree is one where all the nodes have two children except well we have to stop at some point except maybe on this last level there it's fine if some notes uh have no children

14:19 A Complete Binary Tree

14:40 but if so they should be all flush left so we want this um this kind of shape here you want up to the penultimate level every node has exactly two children and then on this on this last level here and up to some point they all need to have two children then there could be one note where potentially has just the left child or none and then the rest have no children okay and that's what we mean by a complete binary tree

15:23 Labels on the Nodes

15:24 and now this last bit is about labels on the nodes um and uh as the as The annotation says if you have labels assigned to each of these nodes in the binary tree so each of these circles additionally has not just not just left and right pointers but also a value element then every parent should have a label that's larger than the labels of all its children and if you think about if this is true then the root must be the the largest element in the entire thing just by induction right the the root is bigger than its children and these are bigger than their children and so on and so forth okay now we have these two two things that uh both seem to have some notion of slightly ordered but what what really brings them together is this notion of level order so let me draw another little complete binary tree

16:34 Level Order

16:38 and level order means we go through this tree level by level and we assign indices to the notes as we visit them one two three four five six seven eight nine ten

16:55 okay if you do that and you write the labels of these nodes so the green ones are indices in this level ordered traversal uh the notes would also have some some values associated with them so you could write down an array where you have the

17:36 the first element would be the label of the roots which as we figured out must be the biggest the maximum of the of the array I don't know I can peek at my example so this will be probably doesn't match with the numbers oh but I accidentally does okay uh so I'm just putting in some numbers here

18:00 that could be there they're arbitrary in a way okay and they'll match the example on the next slide I just wanted to put them here as well so that you can check uh for any position if I go to say position seven if I have seven and round down that's three so I should check 70 is bigger than 10. that sounds right and that should be true for all the positions and that's not really magic if you see where seven and three are in this three then three is here 7 is here so aha 7 is a child of three and you can work out that this is exactly what happens uh taking an index and halfing it round down is going to the parent all right so the two things are the same you can either write it as an array with satisfying this this weird condition or you can have a complete binary tree with Heap order on the labels the same thing all right

19:12 here's a bigger example where I put instead of the the circles I just put the labels in that's the same tree as we had on the slide before so whenever you walk from the root downwards uh to some Leaf you follow a path that is uh strictly decreased as that's decreasing doesn't need to be strict I haven't said that so in a way it's it's slightly sorted in this sense right there's there's many paths you can follow which are sorted and if you think back how they look in the array they go basically from left to right but they skip many elements in between

19:51 okay so that's a lovely definition uh but why why would you want to work with such a weird structure right now in anticipation of what comes let me copy this already

20:13 I'm going to motivate before we see why it's useful why why maybe this is a good idea or it's convenient question so you could even rent all like financials of nervous uh yeah so the question is can you can you generalize this kind of mapping from tree to an array to arbitrary trees uh in a way yes and no um you can always do it but you might waste a lot of space or you need to think of some other way so I suppose the root has just a single child and that say that's a right child not a not a left child you want to kind of um retain that information um and so that means you know if the root has just a single child also the next level has just one node and so you're you're having a gap in this level order and you need a mechanism to either memorize where the gaps are or you need to leave space for the largest complete tree that contains the one that you're representing and that might be exponentially bigger uh but yeah it's a it's a useful concept to linearize data structures like this because working with arrays is usually much faster jumping to a specific index is usually faster than following

21:43 pointers in our case the the shape of this tree is quite convenient and I want to motivate y so why do we have complete binary trees here first of all it's simple because there's really for every size for every number of nodes there's a single shape the tree can take there's a single full single complete binary tree with n nodes because everything's prescribed it has to be completely filled at the pair up to the penultimate level and then everything else is flush left so there's really no leeway uh another good thing about these is we'll see that we'll have to work down paths from the route to the Leafs and if you've seen heaps before you know that so having trees with a small height is good and the complete binary trees are the ones other the binary trees with minimal height for a given set of nodes intuitively just because we stuck all the notes as high up as possible until there's no space left so how would you possibly improve upon that uh whereas in general the binary tree could be a long chain of just left left links so that could have linear height whereas this one um has logarithmic height as we'll as we'll see

21:55 Complete Binary Trees

23:10 and then lastly the facts that's why the question was was really helpful here um the fact that we have this completeness that we fill up all the levels up to where possible means that we have these very simple formulas to go from a node to its children or to its parent okay

23:31 Heap Order

23:31 the second bit of the definition was Heap order and that was more obvious I think at least one one thing is obvious if the maximum's at the root that's good if we want to find the maximum then we can just uh look at the root and we know it now deleting the maximum the other key operation in priority queues will have to work a bit harder but it's doable the other thing is it is it is sorted but only only very mildly so in a way there's many many leaves which are completely unordered if you think about it nothing tells you if two siblings are ordered this way or that way there's no restriction so there are still many many uh many assignments of the labels to a heap left that are valid and we'll exploit that for fast insert

24:40 with the number of numbers the heights logarithmic I haven't told you how the insert Works yet in a way but you're you will be right in a way yeah

25:02 yeah that's that's true uh eventually the operations Are all uh dominated by The Heights in one way or another and that uh that means they're logarithmic at the end of the day

25:15 uh we have this question that I I didn't really discuss so by now we should have seen the right answer uh just to recap that