- [Instructor] Hi there.
Now we're gonna implement heap sort in C++.
And we've been to this party before,
so you know what I'm gonna do.
I'm gonna create a source file.
heapSort.cpp.
And I'm gonna go and grab a little snippet here
from this file where we have our print vector
and our include statements.
Those have been our familiar friends.
And let's start as we've done so many times before
by getting our function signatures squared away first.
So I'm gonna borrow this snippet of code here
for the templating
and we're going to have,
as I alluded to in the previous video
a percolateDown method,
function I should say percolateDown
and that's gonna take a std::vector of Comparables
and we'll call that v as we've been doing all along.
And we're gonna have two additional parameters.
Int start and int, oops, look at me typing and, int end.
And that's percolateDown.
Then we're going to have a function called heapify.
Void heapify
and that is going to take a vector
of Comparables.
Call it v.
And it's going to take an additional parameter, the size.
The size of the vector.
And that's the function that we're going to use
to take our input vector,
our unsorted input vector
and turn it into a heap.
Then we're going to have a heapSort algorithm or function.
Void heapSort.
And that's gonna take a vector.
And finally, we're gonna have main.
I'm gonna add one more
but you'll see when we come to it what I'm doing.
Int main and return zero.
Okay.
Now, heapSort is gonna be the function
that we're gonna call to sort our vector.
It's going to call heapify once
to turn the vector into a heap, a binary heap,
satisfying the structure property
and the heap order property.
And then we've gonna use this function quite a bit,
percolateDown because every time we delete the root,
we're going to have
to start calling that percolateDown function
until we find a place for the newly orphaned value.
So where do we start?
Let's start with heapify.
Actually no, let's start with percolateDown.
Okay, so percolateDown,
we're gonna start at the root
and we're gonna keep swapping
until we find the correct place for the value, okay?
So let's create a variable here,
int root equals start
and we're gonna start off with the root
and this might be a sub tree
and as we update root,
we're moving to a sub tree or a sub sub tree
or a sub sub tree as we work our way
through this algorithm.
And then we're gonna have a while loop
and before we fill this out,
let's stop and think what we're doing here.
If we have a value that we wanna percolateDown,
we're going to first look at the children.
There are gonna be two of them.
A left child and a right child.
And we're going to want to choose the larger of the two.
If they're equal, we pick one, it doesn't matter.
But we choose the larger of the two
to perform the swap and then we do the swap.
So what we're going to need to here
in this while loop is the index of the left child.
And we can calculate the index of the left child
of any element in our binary heap
if the index of our element is i.
If the index, oops,
of our element is i,
then left child index
will be two times i
plus one and you recall,
there's a mapping between the elements
and a binary heap
and their indices and a vector.
We saw we could move back and forth
between the tree representation
and the vector representation with ease
and that's how we can calculate this value.
So we can calculate the left child index
by 2i plus one.
Now, since we're going to do that quite often,
I'm gonna create a helper function to do that
and this is something we haven't seen before.
It's gonna use the inline keyword.
Int, and I'll explain what that is in a second,
leftChild int i.
And it's just gonna return
two times i plus one.
And now what the compiler is gonna do,
this inline keyword is telling the compiler
wherever you find this function,
just expand it in place, okay?
So that's what's gonna happen.
But you can think of it as calling a function
and not worry about what the compiler thinks.
So we're gonna say while leftChild
of the root, whatever that is,
oops, toop, look at me, root.
(instructor chuckling)
Is less than or equal to end.
Okay?
Then we're gonna perform a test.
Now remember, we wanna know
which is the larger value of the child,
the left child or the right child.
If the left child is some number j,
then the right child will, the index will be j plus one.
Let's first do this.
Int child.
Oops, child equals leftChild root.
And then we're gonna perform a little test.
If child plus one,
that's the right child,
less than or equal to end,
that means the right child exists,
and the value of child,
that's the left child,
is less than the value of the right child,
okay?
This is saying
there, oops, there is a right child
and its value
is
greater
than that of the left child, okay?
Then we're gonna wanna work with the right child
because that's gonna be the bigger of the two
that we're gonna perform the swaps on.
So we'll increment child.
Child was pointing to the left child.
Now it's gonna point to the right child
because we've performed this test.
And now we continue.
So that's what we've just done here
is how we determine
which child to do the swapping with, okay?
And so if
the root
less than v child,
which is now choosing the correct child,
the greater of the two, then we're gonna swap.
And then we're gonna do this whole swap thing.
Comparable temp equals v root.
V root gets v child.
Whatever that is, the left child or the right child.
V child gets temp
and that completes our swap.
And if this condition isn't true,
then we're just gonna return.
Then we've found a good spot.
Return, okay?
So that's our percolateDown function.
Now, we can implement heapify
'cause heapify needs that percolateDown function.
So in heapify,
we're gonna create a variable integer
start equals size minus two
divided by two, oops, sorry, divided by two.
Okay.
Now, what's going on here.
We're passing in a vector v
and we're passing in an integer size,
which is the size of our vector.
And what does this do?
Well, I knew we were gonna get to this,
so I prepared a little illustration.
So let me role out to that.
Here we have a binary heap
and what I'm showing here
are not the values of the binary heap
but the indices of the binary heap,
so this is index zero, index one, index two,
index three, index four, index five, index six, okay?
And we have seven elements
in our binary heap
and if we use that formula,
n minus two divided by two,
and that's integer division,
n minus two is five,
five divided by two is gonna be 2.5 truncated to two.
So if n is seven,
then that's gonna choose this guy.
Okay, and what we have done?
When we're creating our heap,
we wanna start with the rightmost element
in the next to last layer,
and start our percolation from there.
So this formula, n minus two divided by two,
integer divided by two
is always going to find the rightmost element
with children in the next to last layer of the heap.
Let's look at another example.
Here we have n equals eight.
So n minus two is six
divided by two, that's six divided by two is three.
That's gonna choose this guy.
And then again,
you see that's the rightmost node
in the tree in the next to last level of the tree
that has a child.
And we'll do one more example.
Here's n equals five.
N minus two divided by two
is three divided by two.
That's 1.5 truncated to one
and we're picking this node.
And so here this again is the rightmost node
in our heap in the next to last level with children.
And so that's what this little formula does.
So to go back to our code,
that's what we've done here.
We're choosing the element
where we want to start our percolation
when we convert to a heap.
And then this is a simple process.
Then what we're gonna do is we have a while loop.
Start greater than, equal to zero
while we haven't gone all the way through the heap yet.
We percolateDown with v, start
and size -1 because that's an index, okay?
We're passing in start and end indices.
And then when we're done with that,
we decrement start.
So we're gonna count down, let's go back to this,
we're gonna count down, let's pick this one,
we're gonna start here,
we're gonna percolateDown
and then we're gonna decrement three,
so then we're gonna start here
and we're gonna do our percolations
and then we're gonna decrement,
we're gonna do here
and we're gonna do our percolations
and then finally, we percolateDown from the root.
And after we've performed all of those percolations
and completed all those processes,
we'll have a binary heap instead of just an unsorted vector.
So that's our heapify function.
And now heapSort.
So let's see.
We're gonna need an integer
and we're just gonna call it size.
And that's gonna be v.size.
Okay?
So we don't have to call that more than once.
Integer end
equals size
minus one, 'cause that an index
and then another while loop.
While end, oops, sorry, oh, end
greater than zero.
We're gonna do this swap
and you'll recall the swap that we were doing
was we're taking the element at the root
and swapping it with the last element
in the heap.
Okay?
So we're going to do a swap Comparable temp
equal v end,
getting the value at the end
and then v end
gets v subzero,
the one at the root,
and then v root gets the temp,
so that's assigning the value that was at the end.
And then we decrement end.
And then we percolateDown
because after every deletion of the element at the root,
we have to restore the heap order property
by percolating down
and we're gonna pass in v, zero and end.
And notice, we decremented n
because now we have one fewer unsorted element
that remains in our heap.
And then we're just gonna printVector.
V.
And that's heapSort.
Now let's test it.
We've got std::vector of ints,
v, and we'll give it that same vector we've been using
for a number of other examples,
eight, five, zero, four, three, nine, one,
seven, two, six.
So there's our unsorted vector.
And let's print it.
printVector.
V, and then we'll call heapSort.
You know what?
I'm gonna add one more thing here.
What I'm gonna do is I'm gonna show the result
of heapify, okay?
So oh, I left that out, look at me.
Heapify, good thing I did this.
Heapify.
I forgot to call heapify.
V, size.
Okay.
So what we'll do here
is we'll put a little note here.
Std::cout
Heapify
and this is just so we see what's going on in the output.
Std::endL
and then we'll put a printVector here too.
And a little divider.
So we show what happens
when the vector comes in.
It gets heapified
and then everything below this line is gonna be the results
of this while loop.
We're gonna go through that while loop n times, okay?
So that should do it.
So let's run it and make sure it works.
Okay, that doesn't look right.
Where did I go wrong?
Sorry.
heapSort.
Looks right.
Heapify.
It's gotta be in here some place.
percolateDown.
Oh I see, okay.
I made a mistake here.
I left something out.
Root equals child.
Ha ha ha.
So I forgot this very important step here,
which is as we're percolating down,
once we percolateDown,
now we start at a new point
for the next percolation, if needed.
Okay, so that's why we assign the value of root as child
and now this isn't really the root,
it's really the root of a sub tree, okay?
So just remember that this is the root
of a sub tree and not necessarily the root
of the tree itself as we're percolating.
So sorry about that booboo.
All right, let's try this again.
Hey, there we go.
Okay, so let me expand this a little bit.
So this here is our beautiful input vector
and that matches what we have here.
Eight, five, zero, four, blah, blah, blah.
And then this is to let us know what's going on here.
This is where we call heapify
and heapify turns it into this vector here
and this has the heap order property.
Let's just walk through this.
Nine is at the root
and the children are seven and eight.
Seven and eight are less than nine.
And seven is the left child
and the children of the left child are five and six,
both less than seven.
Here's eight, the children of eight are zero and one.
And then, so you see, this has the heap order property
and that's good.
And then as I said,
we have nine calls or nine iterations of that loop,
that while loop.
And you see the sorted values,
the largest values, because this is a max heap accumulating
on the right.
So after the first iteration,
we have nine and this is our heap
and then at the second iteration,
we have eight and nine.
And this is our remaining heap
and notice, eight is at the root here,
seven is at the root here.
See all these six, five, four, three,
two, one, zero down here,
so the largest value is always winding up at the root
after we restore the heap order property.
Now we have these three sorted values
and this is our heap.
And again, we can check the heap order properties
on these, six is at the root,
five and three are smaller than six,
four and two are smaller than five.
Zero and one are smaller than three.
See, it's got the heap order property.
Next iteration, six, seven, nine.
Six, seven, eight, nine.
Next iteration, five, six, seven, eight, nine.
Four, five, six, seven, eight, nine.
See, so our sorted portion is getting bigger.
Our unsorted portion is getting smaller
and then when we're done,
we've got our sorted vector
and that is heap sort.
Sorry about the mistake
but I'm glad I was able to spot it quickly
and that brings our study
of sorting to a close.
And now we're gonna move on to hashing
and that will be coming up in subsequent videos.
Thanks very much. Bye bye.