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.