0:00

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

Â 8:08

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.

Â 16:09

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.

Â