So in this video, we'll start talking about the heap data structure. So in this video I want to be very clear on what are the operations supported by heap, what running time guarantees you can expect from [inaudible] limitations and I want you to get a feel for what kinds of problems they're useful for. In a separate video, we'll take a peek under the hood and talk a little bit about how heaps actually get implemented. But for now, let's just focus on how to use them as a client. So the number one thing you should remember about a given data structure is what operations it supports, and what is the running time you can expect from those operations. So basically, a heap supports two operations. There's some bells and whistles you can throw on. But the two things you gotta now is insertion and extract min. And so the first thing I have to say about a heap is that it's a container for a bunch of objects. And each of these objects should have a key, like a number so that for any given objects you can compare their keys and say one key is bigger than the other key. So for example, maybe the objects are employee records and the key is social security numbers, maybe the objects are the edges of a network and the keys are something like the length or the weight of an edge, maybe each object indicates an event and the key is the time at which that event is meant to occur. Now the number one thing you should remember about a given data structure is, first of all what are the operations that it supports? And second of all, what is the running time you can expect from those operations? For a heap, essentially there's two basic operations. Insert and extract the object that has the minimum key value. So in our discussion of heaps, we're going to allow ties that are pretty much equal to easy with or without ties. So, when you extract men from a heap they may have duplicate key values then there's no specification about which one you get. You just get one of the objects that has a tie for the minimum key value. Now, of course, there's no special reason that I chose to extract the minimum rather than the maximum. You either you can have a second notion of a heap, which is a max heap, which always returns the object of the maximum key value. Or if all you have at your disposal is one of these extract min-type heaps, you can just, negate the sign of all of the key values before you insert them, And then extract min will actually extract, the max key value. So, just to be clear, I'm not proposing here a data structure that supports simultaneously an extract-min operation and an extract-max operation. If you wanted both of those operations, there'd be data structures that would give it to you; probably a binary search tree is the first thing you'd want to consider. So, I'm just saying, you can have a heap of one off two flavors. Either the heap supports extract-min and not extract-max or the heap will support extract-max and not extract-min. So I mentioned that you should remember not just the supported operations of a data structure, but what is the running time of those operations. Now, for the heap, the way it's canonically implemented, the running time you should expect is logarithmic in the number of items in the heap. And its log base two, with quite good constants. So when you think about heaps, you should absolutely remember these two operations. Optionally, there's a couple other things about heaps that are, might be worth remembering Some additional operations that they can support. So the first is an operation called heapify. Like a lot of the other stuff about heaps, it has a few other names as well. But I'm going to call it heapify, one standard name. And the point of heapify is to initialize a heap in linear time. Now, if you have N things and you want to put them all in a heap, obviously you could just invoke insert once per each object. If you have N objects, it seems like that would take N times log N time, log N for each of the N inserts. But there's a slick way to do them in a batch, which takes only linear time. So tha t's the heapify operation, And another operation which can be implemented, although there are some subtleties. Is you can delete not just the minimum, but you can delete an ar-, arbitrary element from the middle of a heap, again, in logarithmic time. I mention this here primarily cuz we're gonna use this operation when we use heaps to speed up Dijkstra's Algorithm. So that's the gist of a heap. You maintain objects that have keys you can insert in logarithmic time, and you can find the one with the minimum key in logarithmic time. So let's turn to applications, I'll give you several. But before I dive into any one application let me just say; what's the general principle? What should [inaudible] you to think that maybe you want to use a heap data structure in some task? So the most common reason to use a heap is if you notice that your program is doing repeated minimum computations. Especially via exhaustive search, Most of the applications that we go through will have this flavor. It will be, there will be a naive program which does a bunch of repeated minimums using just brute force search and we'll see that a very simple application of a heap will allow us to speed it up tremendously. So let's start by returning to the mother of all computational problems, sorting and unsorted array. Now, a sorting algorithm which is sort of so obvious and suboptimal that I didn't even really bother to talk about it at any other point in the course is selection-sort. What do you do? In selection sort, you do a scan through the unsorted array. You find the minimum element; you put that in the first position. You scan through the other N-1 elements; you find the minimum among them. You put that in the second position. You scan through the remaining N-2 unsorted elements. You find the minimum; you put that in the third position, and so on. So evidently, this [inaudible] sorting algorithm does a linear number of linear scans through this array. So this is definitely a quadratic time algorithm. That's why I didn't bother to tell you about it earlier. So this certainly fits the bill as being a bunch of repeated minimum computations. Or for each computation, we're doing exhaustive search. So this, we should just, a light bulb should go off, and say, aha! Can we do better using a heap data structure? And we can, and the sorting algorithm that we get is called heap sort. And given a heap data structure, this sorting algorithm is totally trivial. We just insert all of the elements from the array into the heap. Then we extract the minimum one by one. From the first extraction, we get the minimum of all N elements. The second extraction gives us the minimum of the remaining N-1 elements, and so on. So when we extract min one by one, we can just populate a sorted array from left to right. Boom, we're done. What is the running time of heap sort? Well, we insert each element once and we extract each element once so that's 2n heap operations and what I promised you is that you can count on heaps being implemented so that every operation takes logarithmic time. So we have a linear number of logarithmic time operations for running time of n log n. So let's take a step back and appreciate what just happened. We took the least imaginative sorting algorithm possible. Selection sort, which is evidently quadratic Time. We recognize the pattern of repeated minimum computations. We swapped in the Heap Data structure and boom we get an NlogN sorting algorithm, which is just two trivial lines. And remember, N log N is a pretty good running time for a sorting algorithm. This is exactly the running time we had for merge sort; this was exactly the average running time we got for randomized quick sort. Moreover, Heap Sort is a comparison based sorting algorithm. We don't use any data about the key elements we just used as a totally [inaudible] set. And, as some of you may have seen in an optional video, there does not exist a comparison-based sorting algorithm with running time better than N log N. So for the question, can we do better? The answer is no, if we use a comparison based sorting algorithm like heap sort. So that's pretty amazing, all we do is swap in a Heap and a running time drops from really quite unsatisfactory quadratic to the optimal N log N. Moreover, HeapSort is a pretty practical sorting algorithm: when you run this it's gonna go really fast. Is it as good as quick sort? Hm, maybe not quite but its close it's getting into the same [inaudible]. So let's talk of another application which frankly in some sense is almost trivial but this is also a canonical way in which heaps are used. And in this application it will be natural to call a heap by a synonymous name, a priority queue. So what I want you to think about for this example is that you've been tasked with writing software that performs a simulation of the physical world. So you might pretend, for example, that you're helping write a video game which is for basketball. Now why would a heap come up in a simulation context? Well, the objects in this application are going to be events records. So an event might be for example that the ball will reach the hoop at a particular time and that would be because a player shot it a couple of seconds ago. When if for example the ball hits the rim, that could trigger another event to be scheduled for the near future which is that a couple players are going to vie for the rebound. That event in turn could trigger the scheduling of another event, which is one of these players? commits, an over the back foul on the other one and knocks them to the ground. That in turn could trigger another event which is the player that got knocked on the ground gets up and argues that a foul call, and so on. So when you have event records like this, there's a very natural key, which is just the timestamp, the time at which this event in the future is scheduled to occur. Now clearly a problem which has to get solved over and over and over again in this kind of simulation is you have to figure out what's the next event that's going to occur. You have to know what other events to schedule; you have to update the screen and so on. So that's a minimum computation. So a very silly thing you could do is just maintain an unordered list of all of the events that have ever been scheduled and do a linear path through them and compute the minimum. But you're gonna be computing minimums over and over and over again, so again that light bulb should go on. And you could say maybe a heap is just what I need for this problem. And indeed it is. So, if you're storing these event records in a heap. With the key being the time stamps then when you extract them in the hands for you on a silver platter using logarithmic time exactly which algorithm is going to occur next. So let's move on to a less obvious application of heaps, which is a problem I'm going to call median maintenance. The way this is gonna work is that you and I are gonna play a little game. So on my side, what I'm going to do is I'm going to pass you index cards, one at a time, where there's a number written on each index card. Your responsibility is to tell me at each time step the median of the number that I've passed you so far. So, after I've given you the first eleven numbers you should tell me as quickly as possible the sixth smallest after I've given you thirteen numbers you should tell me the seventh smallest and so on. Moreover, we know how to compute the median in linear time but the last thing I want is for you to be doing a linear time computation every single time step. [inaudible] I only give you one new number? Do you really have to do linear time just to re-compute the median? If I just gave you one new number. So to make sure that you don't run a linear time selection algorithm every time I give you one new number, I'm going to put a budget on the amount of time that you can use on each time step to tell me the median. And it's going to be logarithmic in the number of numbers I've passed you so far. So I encourage you to pause the video at this point and spend some time thinking about how you would solve this problem. Alright, so hopefully you've thoug ht about this problem a little bit. So let me give you a hint. What if you use two heaps, do you see a good way to solve this problem then. Alright, so let me show you a solution to this problem that makes use of two heaps. The first heap we'll call H low. This equal supports extract max. Remember we discussed that a heap, you could pick whether it supports extract min or extract max. You don't get both, but you can get either one, it doesn't matter. And then we'll have another heap H high which supports extract min. And the key idea is to maintain the invariant that the smallest half of the numbers that you've seen so far are all in the low heap. And the largest half of the numbers that you've seen so far are all in the high heap. So, for example, after you've seen the first ten elements, the smallest five of them should reside in H low, and the biggest five of them should reside in H high. After you've seen twenty elements then the bottom ten, the smallest ten, should, should reside in H low, and the largest ten should reside in H high. If you've seen an odd number, either one can be bigger, it doesn't matter. So if you have 21 you have the smallest ten in the one and the biggest eleven in the other, or vice-versa. It's not, not important. Now given this key idea of splitting the elements in half, according to the two heaps. You need two realizations, which I'll leave for you to check. So first of all, you have to prove you can actually maintain this invariant with only O of log I work in step I. Second of all, you have to realize this invariant allows you to solve the desired problem. So let me just quickly talk through both of these points, and then you can think about it in more detail, on your own time. So let's start with the first one. How can we maintain this invariant, using only log I work and time step I, and this is a little tricky. So let's suppose we've already processed the first twenty numbers, and the smallest ten of them we've all worked hard to, to put only in H low. And the biggest ten of th ''em we've worked hard to put only in H high. Now, here's a preliminary observation. What's true, so what do we know about the maximum element in h low? Well these are the tenth smallest overall and the maximum then is the biggest of the tenth smallest. So that would be a tenth order statistic, so the tenth order overall. Now what about in the, the hi key? What s its minimum value? Well those are the biggest ten values. So the minimum of, of the ten biggest values would be the eleventh order statistic. Okay, so the maximum of H low is the tenth order statistic. The minimum of H high Is the [inaudible] statistic, they're right next to each other; these are in fact the two medians Right now So When this new element comes in, the twenty-first element comes in, we need to know which heap to insert it into and well it just, if it's smaller than the tenth order statistic then it's still gonna be in the bottom, then it's in the bottom half of the elements and needs to go in the low heap. If it's bigger than the eleventh order statistic, if it's bigger than the minimum value of the high heap then that's where it belongs, in the high heap. If it's wedged in between the tenth and eleventh order of statistics, it doesn't matter. We can put it in either one. This is the new median anyways. Now, we're not done yet with this first point, because there's a problem with potential imbalance. So imagine that the twenty-first element comes up and it's less than the maximum of the low heap, so we stick it in the low heap and now that has a population of eleven. And now imagine the twenty-second number comes up and that again is less than the maximum element in the low heap, so again we have to insert it in the low heap. Now we have twelve elements in the low heap, but we only have ten in the right heap. So we don't have a 50. 50, 50 split of the numbers but we could easily re-balance we just extract the max from the low heap and we insert it into the high heap. And boom. Now they both have eleven, and the low heap has the smallest el even, and the high heap has the biggest eleven. So that's how you maintain, the invariant that you have this 50/50 split in terms of the small and the high, and between the two heaps. You check Where it lies with respect to the max of the low heap and the mid of the high heap. You put it in the appropriate place. And whenever you need to do some re-balancing, you do some re-balancing. Now, this uses only a constant number of heap operations when a new number shows up. So that's log I work. So now given this discussion, it's easy to see the second point given that this invariant is true at each time step. How do we compute the median? Well, it's going to be either the maximum of the low heap and/or the minimum of the high heap depending on whether I is even or odd. If it's even, both of those are medians. If I is odd, then it's just whichever heap has one more element than the other one. So the final application we'll talk about in detail in a different video. A video concerned with the running time of Dijkstra's shortest path algorithm. But I do wanna mention it here as well just to reiterate the point of how careful use of data structures can speed up algorithms. Especially when you're doing things like minimum computations in an inner loop. So Dijkstra's shortest path algorithm, hopefully, many of you have watched that video at this point. But basically, what it does is it has a central wild loop. And so it operates once per vertex of the graph. And at least naively, it seems like what each iteration of the wild loop does is an exhaustive search through the edges of the graph, computing a minimum. So if we think about the work performed in this naive implementation, it's exactly in the wheel-house of a heap, right. So what we do in each of these loop iterations is do an exhaustive search computing a minimum. You see repeated minimum computations, a light bulb should go off and you should think maybe a heap can help. And a heap can help in Dijkstra's algorithm. The details are a bit subtle, and they're discussed i n a separate video, but the upshot is, we get a tremendous improvement in the running time. So we're calling that M denotes the number of edges. And N denotes the number of vertices of a graph. With a careful deployment of heaps in Dijkstra's algorithm, the run time drops from this really rather large polynomial. The product of the number of vertices and the number of edges. Down to something which is almost linear time. Anyway, o of m log n. Where m is the number of edges and n is the number of vertices. So the linear time here would be o of m. The liner of the number of edges we're picking up an extra log factor but still this is basically as good as sorting. So this is a fantastically fast shortest path algorithm. Certainly, way, way better that what you get if you don't use heaps and do just repeated exhaustive searches for the minimum. So that, that's wraps up our discussion of what I think you really want to know about heaps. Namely, what are the key operations that it supports? What is the running time you can expect from those operations? What are the types of problems that the data structure will yield speed ups for? And a suite of applications. For those of you that want to take it to the next level and see a little bit about the guts of the implementation, there is a separate optional video that talks a bit about that.