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 a heap, what running time guarantees you can expect from canonical
implementations, 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 that you can throw on, but the
two things you got to know is insertion and extract min.
Alright. So, the first thing I have to say about a
heap is that's 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 the edge.
Maybe each object indicates an event and the key is the time 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 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. They're pretty much equally easy with or
without ties. So when you extract min 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.
either you could have second notion of the heap, which is the max heap, which
always returns the object to the maximum key value, or if all you have it, 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 or 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 of 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
economically implemented, the running time you should expect is logarithmic in
the number of items in the heap. That's 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 of other
things about heaps that 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 login time.
Login for each of the n inserts. But there's a slick way to do them in a
batch, which takes only linear time. So that's the heapify operation.
And another operation which can be implementedn 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 algorithmic time.
I mention this here primarily because we are going to 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 trigger 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. And most of the applications that we go
through will have this flavor. It'll be, there'll 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
really even bother to talk about it in any other point in the course, is
selection sort. When you do 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 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 the 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 a running time of N log N.
So, let's a step back and appreciate what just happened.
We took the least imaginative sorting algorithm possible, selection sort, which
is evidently quadratic time. We recognized the pattern of repeated
minimum computations. We swapped in the heap data structure and
boom, we get an N log N 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 mergesort. This was exactly the average running time
we got from randomized quicksort. Moreover, heapsort is a comparison-based
sorting algorithm. We don't use any data about the key
elements, we just used it as a totally ordered 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 the right time drops
from the really quite unsatisfactory quadratic to the optimal N log N.
Moreover, heapsort's a pretty practical sorting algorithm. You run this, it's
going to go really fast. Is it as good as Quicksort?
Mm-hm, maybe not quite. But it's close, it's getting into the same ballpark.
So, let's look at another application which, which frankly, in some sense, is
almost trivial. but this is also a connotical 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 writing 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 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 him to
the ground. That in turn could trigger another event
which is, the player that got knocked on the ground, gets up and argues the foul
call, and so on. So when you have event records like this,
there's a very natural key, which is just the time stamp. The time in 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 that's going
to occur. You have to know what other events to
schedule, you have to know how to update the screen, and so on.
So, that's a minimum computation. So, a very silly thing you can do is just
maintain an unordered list of all of the list that have ever been scheduled, and
do a linear pass through them and compute the minimum.
But you're going to be computing the minimums over and over and over again.
So again, that light bulb should go on and you can 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 min, the heap hands for you on a silver platter
using only logarithmic time exactly which event 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 that this is going to work is you
and I are going to 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 when there's a number written on
each index card. Your responsibility is to tell me at each
time step the median of the numbers that I passed you so far.
So, after I've given you the first eleven numbers, you should tell me as quickly as
possible the six smallest. After I've given you the thirteen numbers, you
should tell me the seven 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.
But I will only give you one new number. Do you really have to do linear time is
to recompute 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 at 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 thought 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.
So the first heap we'll call H low, this heap will support 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
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 and the one and the biggest eleven
and 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 eventually maintain this invariant
with only O of log i worked and step i. Second of all, you, after you 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 at time step i?
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 them only in H low.
And the biggest ten of them 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 will be the tenth order statistic, so the tenth smallest overall.
Now, what about in the high heap, what is its minimum value?
Well, those are the biggest ten values, so the minimum 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 eleventh order 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 21st element comes in, we need to
know which heap to insert it into. And well, if it's smaller than the tenth
order statistic then it's still going to be in the bottom, then it's in the bottom
half of the elements. It 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 statistics, it doesn't matter.
We can put it in either one, this is the new medium anyways.
Now, we're not done yet with this first point because there's a problem with
potential imbalance. So, imagine that the 21st 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 22nd 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 split of
the numbers. But, we can easily rebalance.
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 eleven and
the high heap has the biggest eleven. So, that's how you maintain the
invariants that you have this 50-50 split in terms of the small and the high and
the two heaps. You check where it lies with respect to
the max of the low heap and the min in the, of the high heap.
You put it in the appropriate place. And whenever you need to do some
rebalancing, you do some rebalancing. And 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 than 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 want to 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 man 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 while loop does is it exhaustive search to 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 remeded, 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 in this 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 then denotes the number of vertices of a graph.
With the careful deployment of heaps in Dijkstra's algorithm, the run time drops
from this really rather large polynomial, the product of a number of vertices and
the number of edges, down to something which is almost linear time.
Namely 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.
Linear, the number of edges, were 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 than what you get if you don't use heaps, and just do
repeated exhausted searches for the minimum.
So that wraps up our discussion of what I think you really want to know about
heaps. Namely, what are the key operations that
is supports. What is the running time you could expect
from those operations. What are the types of problems that the
data structures will yield speed ups for, and a suite of applications.
For those of you who 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
little bit about that.