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.