So, in this video, we're gonna take it at least partway to the next level for the
heap data structure. That is, we'll discuss some of the implementation
details. I.e., how would you code a, a heat data structure from scratch? So
remember what the point of a heap is. It's a container, and it contains objects, and
each of these objects, in addition to possibly lots of other data, should have
some kind of key. And we should be able to compare the keys of different objects; you
know, Social Security numbers for different employers, edge weights for
different edges in a network, or time stamps on different events, and so on. Now
remember, for any data structure the number one thing you should remember is
what are the operations that it supports, i.e., what is the data structure good for.
And also, what is the running time you can count on of those operations. So something
we promised in a previous video. [inaudible] Indicate the implementation of
the miss video is these two primary operations that a heap exports. First of
all, you can insert stuff into it, and it takes [inaudible] logarithmic in the
number of objects that the heap is storing. And second of all, you can
extract an object. That has the minimum key value, and again we're going to allow
duplicates in our, in our heaps, so if there's multiple objects, then I'll have a
minimum, a common minimum key value, the heap will return one of those. It's
unspecified, which one. As I mentioned earlier, you can also dress up heaps with
additional operations, like you can do batch inserts, and you can do linear time
rather than log in time. You can delete from the middle of the heap. I'm not gonna
discuss those in the video; I'm just going to focus on how you'd implement inserts
and extract [inaudible]. If you wanna know how heaps really work, it's important to
keep in mind simultaneously Two different views of a heap One, as a tree And one, as
a, array. So we're gonna start on this slide with the tree view. Conceptually,
this will be useful to explain how the heap ope rations are implemented. A
conceptual will think of a heap not just as any old tree, but as a tree that's
rooted. It'll be binary. Meaning that, each node will have zero, one or two
children nodes And third, it will be as complete as possible. So let me draw for
your amusement an as complete as possible binary tree that has nine nodes. So if the
tree had, had only seven nodes it would have been obvious what, is complete as
possible means. It would have meant we just would have had three completely
filled in levels. If it had, had fifteen nodes it would have had four completely
filled in levels. If you're in between, these two numbers that are powers of two
minus one, well we're going to call a complete to the tree as just in the bottom
level you fill in the leaves from left to right. So here the two extra leaves on the
fourth level are both, pushed as far to the left as possible. So, in our minds,
this is how we visualize heaps. Let me next define the heat property. This
imposes an ordering on how the different objects are arranged in this tree
structure. The heap property dictates that at every single node of this tree it
doesn't matter if it's the root if it's a leaf if it's an internal node whatever. At
every node X the key of the object stored in X should be no more than the keys of Xs
children. Now X may have zero children if it's a leaf it may have one child or it
may have two children whatever those cases zero one or two children all those
children keys should be at least that of key at X. For example, here is a heap with
seven nodes. Notice that I am allowing duplicates. There are three different
objects that have the key value four, in this heap. Another thing to realize is
that while the heap property imposes useful structure on how the objects can be
arranged it in no way uniquely pins down their structure. So this exact same set of
seven keys could be arranged differently and it would still be a heap. The
important thing is that, in any heap, the root has to have a minimum value key. Just
like in the se two organizations of these seven keys, the root is always a four, the
minimum key value. So that's a good sign, given that one of the main operations
we're supposed to. Quickly implement, is to extract the minimum value. So at least
we know where it's going to be, it' gonna be at the root of a heap. So while in or
minds we think of heaps as organized in a tree fashion, we don't literally implement
them as trees. So in something like search trees, you actually have pointers at each
node and you can traverse pointers to go from a [inaudible] to the children from
the children to the parents, yada, yada, yada. Turns out it's much more efficient
in a heap to just directly implement it as an array. Let me show you by example how a
tree like we had on the last slide maps naturally onto an array representation. So
let's look at a slightly bigger heap, one that has nine elements. So let me draw an
array with nine positions. Labeled one, two, three all the way up to nine And the
way we're going to map this tree which is in our mind to this array implementation
is really very natural. We're just going to group the nodes of this tree by their
level. So, the root is gonna be the only node at level zero. Then the children of
the roots are level one, their children constitute level two, and then we have a
partial level three, which is just these last two notes here. And now we just stick
these notes into the array, one level at a time. So the roots winds up in the
privileged first position, so that's going to be the, the first, the object which is
the first copy of the four. Then we put in the level one object, so that's the second
copy of the four and the eight, and then we put in level two Which has our third
four along with the two nines. And then we have the last two notes from level three
rounding out the penultimate and final position of the array. And you might be
wondering how it is we seem to be having our cake and eating it, too. On the one
hand we have this nice, logical tree structure. On the other hand we have this
array implementation and we're not wasting any space on the usual pointers you would
have in a tree to traverse between parents and children. So where's the free lunch
coming from? Well the reason is that because we're able to keep this binary
tree as balanced as possible, we don't actually need pointers to figure out who
is whose parent and who is whose child. We can just read that off directly From the
positions in the array. So, let me be a little bit more specific. If you have a
node in the fifth position, I'm assuming I here is not one, right? So the, the root
doesn't have any, does not have a parent But any other, any other objects in
position I does have a parent And what the position that is, depends on, in a simple
way on whether I is even or odd. So if I is even, then the parent is just
[inaudible] the position of I/2, and if I is odd, then it's going to be I/2. Okay,
that's a fraction. So we take the floor that is we round down to the nearest
integer. If I is odd, So for example, the objects in positions two and three have as
their parent the object in position one, and those in four and five have the one in
position two as his parent. Six and seven have as their parents the node in, the
object in position three and so on And of course we can invert this function we can
equally easily determine who the children are of a given node so if we have an
object in position I. Then you notice that the children of I are gonna be at the
position 2i and 2i+1. Of course those may be empty so if you have a leaf of course
that doesn't have any children and then maybe one node that has only one child.
But in the common case of an internal node it's gonna be two children that are gonna
be in positions 2i and 2i+1. So rather than traversing pointers it's very easy to
just go from a node to its parent to either one of its children just by doing
these appropriate trivial calculations with respects to its position. So this
slide illustrates, some of the. Lower level reasons that heaps are quite a
popular data struct ure So the first one, just in terms of storage. We don't need
any overhead at all. We are just. We have these objects; we're storing them directly
In an array, with no extra space. Second of all, not only do we not have to have a
space for pointers But we don't even have to do any traversing. All we do are these
really simple. Divide by two or multiply two operations And using bit shifting
tricks. Those can also be implemented extremely quickly. So, the next two slides
let me indicate, at a high level, how you would implement the two exported
operations, namely insertion and extract [inaudible] in time algorithmic in the
size of the heap And rather than give you any pseudo code, I'm just going to show
you how these work by example. I think it will be obvious how they extended the
general case. I think just based on this discussion, you'll be able to code up your
own versions, of insert and extract [inaudible], if you so desire. So let's
redraw the 9-node heap that we had on the previous slide and again, I'm gonna keep
drawing it as a tree and I'm gonna keep talking about it as a tree but always keep
in mind the way it's really implemented is in terms of these array and when I talk
about the parent of a node, again, what that means is you go to the appropriate
position given the position of the node from where you started. So let's suppose
we have an existing heap, like this blue heap here And we're called upon to insert
a new object. Let's say with a key value K. Now remember heaps are always suppose
to be perfectly balanced binary trees. So if we want to maintain the property that
this tree is perfectly balanced is pretty only one place we can try to put the new
key K and that's as the next leaf. That is it's going to be the new right most leaf
on the bottom level. Or in terms of the array implementation we just stick it in
the first non empty slot in the array And if we keep track of the array size we're
getting constant time of course know where to put the new key. Now whether or not we
can get away with this depends on what the actual key value K is But, you know, for
starters we can say, what if we insert a key that's seven? Well, then we get to
say, whew, we're done. So, the reason we're done is cuz we have not violated the
heap property. It is still the case that every node has key no bigger than that of
its children. In particular, this third copy of a four, it picked up a new child,
but its key seven was bigger than its key four. So, you can imagine that maybe we
get lucky with another insert. Maybe the next insertion is a ten And again, we put
that in the next available spot in the last level And that becomes the second
child of the third copy of the four And again we have no violation of the heap
property. No worries still got a heap And in these lucky events insertion is even
taking constant time. Really all we're doing is putting elements at the end of an
array and not doing any rearranging. So where it gets interesting is when we do an
insertion that violates the heap property. So let's supposed we do yet another
insertion, and the left child of this twelve, it becomes a five. Now we got a
problem. So now we have a as perfectly as possible balanced binary tree, but the key
property is not satisfied. In particular, it's violated at the node twelve. It has
one child. The key of that child is less than its own key. That's no good. So is
there some way we can restore the heap property? Well, a natural idea is just to
swap the positions of the five and the twelve, and that's something that of
course can be done in constant time, cuz again from a node, we can go to the parent
or the child in constant time just with a suitable trivial computation. So we say
okay, for starters we put the five at the end, but that's no good. So we're gonna
swap the five with the twelve And now we see we're not out of the woods. No longer
is there a heap violation at the node twelve. That's been fixed. We've made it a
leaf But we've Pushed up the heap violations. So now instead it's the eight
that has a problem. The eight used to h ave two children, with keys twelve and
nine that was fine. Now the eight has two children with keys five and nine. The five
is less than the eight, that's a violation of the heap property But again, that's the
only violation of the heap property. There's no other node you could have
screwed up, because eight was the only person whose children we messed around
with. Alright So now we just it again. Let's try [inaudible] again, locally fix
the heap violation by swapping the five with the 8s And now we see we've restored
order. The only place where there could possibly be a violation of the heap
property is at the root. The root, when we did this swap, the only person whose
children we really messed with was the root four, and fortunately its new child
has key five, which is bigger than it. One subtle point that you might be thinking
that in addition to screwing up at the root node, that messing around with his
children, maybe we could have screwed up the twill by messing around with its
parent. Alright, its parent used to be five, and now its parent is eight. So is
there some possibility that his parent would all of a sudden have a key bigger
than it But if you think about it, this eight and this twelve, they were a
parent-child relationship in the original heap Right? So back in the blue heap, the
twelve was under the 8s. Now the twelve is under the eight yet again. Since we have
the heap property for that pair before, we certainly have it now. So in general, as
you push up this five up the tree, there's only going to be one possible edge that
could be out of order And that's between where the five currently resides and
whatever its parent is. So when the 5's parent was twelve that was a violation
When 5's parent was eight that was a violation But now that we've pushed it up
two levels and 5's parents is four, that's not a violation because four is less than
five. So in general, step two of insertion is, you do this swap, which it's called a
lot of different things. I'm gonna call it bubble up because that's how I learned it
more years ago than I care to admit But also this is called, sometimes sift up,
happily up, and so on. So now told you to just how to implement insertions by
repeated bubbling ups in a heap data structure And this is really how it works,
there is nothing I haven't told you but you know, I'm not going to really fill in
all the details but I'll encourage you to do that on your own time, if it's
something that interests you And the two main things that you should check is first
of all, is bubbling up process is gonna stop and when it stops, it stops with the
heap property restored. The second thing needs to be checked in this, I think is
easier to see is that we do have the desire one time log [inaudible] make in
the number of elements in the heap. The key observations areas that because this
is a perfectly balanced binary tree. We know exactly how many levels there are. So
this is basically log based two event levels where n is the number of items in
the heap And what is the running time of this insertion procedure while you only do
a constant amount of work at each level, just doing the swap and comparison and
then in the worst case, you'll have to swap at every single level and there is a
lot [inaudible] number of levels. So that's insertion. Let's now talk about how
do we implement the extract [inaudible] operation and again I'm gonna do this by
example and it's gonna be by repeating the [inaudible] of a bubble [inaudible]
procedure. So the Extract main operation is responsible for removing from the heap
an object with minimum key value and handing it back to the client on a silver
platter. So it pretty much have to whip out the root. Remember the minimum is
guaranteed to be at the root. So that's how we have to begin to extract the
subroutine is just we pluck out the root and hand it back to the client. So this
removal of course leaves a gaping hole in our tree structure and that's no good. One
of the [inaudible] responsible for maintaining is that we always have an as
perfectly balanced as possib le binary tree And if you are missing a root you
certainly don't have an almost perfect. Binary tree So, what are we going to do
about it? How do we fill this hole? Well, there's pretty much only one node that
could fill this hole without causing other problems with the tree structure, and that
is the very last node. So the rightmost leaf at the bottom level one that simple
fix is to swap that up and have that take the place of the original root. So in this
case, the thirteen is going to get a massive promotion And get teleported all
the way to be the new root of this tree. So now we've resolved our structural
challenges. We now again have a, as perfectly balanced as possible, binary
tree But of course now we've totally screwed up the heap property, right. So
the heap property says that at every node, including the root, the key value at that
node has to be less than both of the children, and now it's all messed up.
Right, so at the root, the key value's actually bigger than both of the children.
And matters that are little bit more tricky than they were with insertion,
right, when we inserted at the bottom because every note has a unique parent. If
you wanna push a note upward in the tree, there's sort of only one place you can go,
right, all you can do is swap with your parent, unless you're going to try to do
something really crazy But if you want to do something local, pretty much you only
have a unique parent you got to swap with. Now when you're trying to push notes down
to the rightful position in the tree, there is two different swaps you could do,
one for the left child, one for the right child and the decision that we make
matters To see that concretely, let's think about this example. There's this
thirteen at the root, which is totally not where it should be, and there's the two
children. The four and the eight, and we could try swapping it with either one. So
suppose we swap it in a misguided way with the right child, with the eight. So now
the eight becomes the root, and the thirteen gets pushed dow n a level. So on
the one hand; we made some progress because now at least we don't have a
violation between the thirteen and the eight. On the other hand, we still have
violations involving the thirteen. The thirteen is still violated with respect to
the twelve and nine And moreover, we've created a new problem between the eight
and the four, right? So now that the eight is the root, that's still bigger than its
left child, this four. So it's not even clear we made any progress at all when we
swapped the thirteen with the eight, okay? So that was a bad idea And if you think
about it would made it a bad idea, the stupid thing was to swap it with the
larger child. That doesn't make any sense. We really want to swap it with the smaller
child. Remember, every node should have a key bigger than both of its children. So
if we're going to swap up either the four or the eight, one of those is going to
become the parent of the other. The parent is supposed to be smaller, so evidently we
should take the smaller of the two children and swap the thirteen with that.
So we should swap the thirteen with the figure. Not with E And now we observe a
phenomenon very much analogous to what we saw in insert. When we were bubbling up
during insertion, it wasn't necessarily that we fixed violations of the heat
property right away But we would fix one And then introduce another one that was
higher up in the tree And we had confidence that eventually we could just,
push this violation up to the root of the tree And squash it, just like we're trying
to win a game Of Whack a Mole. Here, it's the opposite. It's just in the opposite
direction. So we swap the thirteen with the four. It's true we've created one new
violation of the heap property. That's again involving the thirteen with its
children nine and four. But we haven't created any new ones. We've pushed the
heap violation further down the tree And hopefully again, like in Whack a Mole.
We'll squash it At the bottom. So after swapping the thirteen and the four, now we
just gotta do t he same thing. We say, okay, we're not done. We still don't have
a heap. This thirteen is bigger than both of its children But now, with our
accumulated wisdom, we know we should definitely swap the thirteen with the
four. We're not gonna try swapping with the nine, that's for sure. So we move the
four up here And we, the thirteen takes the 4's old place. Boom! Now we're done.
So now we have no violations remaining. The thirteen in its new position has no
children so there's no way it can have any violations, and the four because it was
the smaller child that's gonna be bigger than the 9's so we haven't introduced a
huge violation there, and again we have these consecutive 4's but we know that's
not gonna be a problem because those were consecutive 4's in the original heap as
well. So you won't be surprised to hear that this procedure by which you push
something down, by swapping it with its smaller children, is called bubble down,
and extract men is nothing more than taking more than, taking this last leaf,
promoting it to the top of the tree, and bubbling down until the heap violation has
been fixed. So again on a conceptual level that's all of the ingredients necessary
for a complete from scratch implementation of extracting the minimum from a heap and
as before, I'll leave it for you to check the details. So first of all you should
check that in fact this bubble down has to at some point halt And when it halts you
do have a bona fide heap. The heap property is definitely restored And second
of all the running time is, is logarithmic. Here the running time
analysis is exactly the same as before so we already have observed that the heights
of a heap because it's perfectly balanced is essentially the log base two of the
number of elements in the heap and in bubbling down all you do is a constant
amount of work per level. All you have to do is a couple comparisons and swap. So,
that's a peek at what's under the hood in the heap data structure. A little bit
about the guts of its elementation. So after having seen this, I hope you feel
like a little bit more hard-core of a programmer, a little bit more hard-core of
a computer scientist.