- [Instructor] The last sorting algorithm
we'll explore is heap sort.
Heap sort makes use of a binary heap.
We use a binary heap to hold our unsorted elements,
and then remove them in sorted order
as we would with a priority queue.
First let's recall from our earlier presentations,
what exactly is a binary heap?
A binary heap is a binary tree with the heap properties.
There are two, first, the tree must be complete.
This means that each level is full
with the possible exception of the last level.
The last level may be incomplete,
but it should be filled from left to right,
we call this the structure property.
The other property is called the heap order property,
and that is that with the exception of the root,
every node must be ordered with respect to its parent.
Well, you'll recall again
that we have two ways that we can order a heap.
We can have a min heap or a max heap.
A min heap is where we have the minimal value at the root,
and then child nodes must have a value
greater than or equal to that of the parent node.
In a max heap, the maximal value is at the root,
and the child nodes must have values
less than or equal to that of the parent node.
For our implementation of heap sort,
and for these demonstrations, we're gonna use max heap.
Let's also recall what happens when we remove the root.
Since we have a max heap, the maximum value is at the root,
and we're gonna sort our vector
by repeatedly removing the element at the root of our heap.
Now, when we delete the root of a binary heap,
we have to restore the heap order property.
And we do that by percolating down
until we find a new position for the orphaned value.
Now, what do I mean by that?
You'll recall from our earlier presentations
that when we removed an element at the root,
we sort of left an empty bubble,
and there was one value in the lowest level
of the binary heap that we needed to find a new home for it,
that's what we call the orphaned value.
And we let that empty bubble percolate down
through the heap until we found a place
where that orphaned value could reside.
Now, what we're gonna do here is we're gonna do this
by performing a series of swaps within our vector.
Now, you may think of heap sort
as an improved selection sort.
Where a selection sort has to scan
the entire unsorted portion of the vector
to find the next element,
heap sort maintains the unsorted data in a binary heap.
And so we can always find the next element
because it's gonna be at the root of the heap.
So when we look at our vector,
we're going to have a portion of our vector
which is a binary heap, and that's our unsorted elements
with the maximum value at the root.
And then we're gonna have a portion of our vector
that has the sorted elements.
Now, of course, when we start,
the entire vector will be a binary heap,
and there will be no sorted elements,
but we'll see the sorted elements
accumulate on the right hand-side of our vector
as we iterate through heap sort.
Here is some high level pseudo code.
Heap sort takes a vector.
We have another function called heapify
which also takes a vector,
and what that does is it takes the vector, the input vector,
and turns it into a binary heap.
It makes the necessary swaps, does whatever we need to do
to turn the input vector into a valid binary heap.
It just does that by swapping.
We'll see more about how that works
when we implement this in C++.
And then we have a while loop.
As long as there are unsorted elements in our vector,
we remove the root from the heap
and append that to our sorted values,
that's gonna be a maximum,
so the largest values will accumulate
on the right-hand side.
And then we have to take steps
to restore the heap order property
on the unsorted elements.
And we'll do that by that percolating down process
that we saw when we introduced binary heaps
a couple weeks back.
So we're gonna need that heapify function
and we're gonna need that percolate down function.
Again, you'll see more of how this works
when we implement heap sort in C++.
But to start,
let's say we have this input vector at the top,
eight, five, zero, four, three, nine,
one, seven, two, six.
And then we use our heapify function
that I referred to earlier
to transform this vector into a valid binary heap.
And this is done by performing the required swaps
to give our vector the heap order property.
Now, if we run heapify, this vector becomes transformed
into this vector, nine, seven eight,
five, six, zero, one, four, two, three.
You may say, well, how do I know that's a binary heap?
Well, let's look at it this way.
Here we have nine at the root,
you'll recall there's a very precise mapping
between the position of elements
in a binary heaps tree representation
with the representation in a vector.
So this nine here is the nine at the root.
Then there's level below that with seven and eight.
Notice that seven and eight are both less than nine.
And then we have another level below that,
five, six, zero, one.
Notice that five and six are less than seven,
zero and one are less than eight,
so, so far the heap order property looks good.
Then we have another level,
notice that this level is not complete
but it is filled from the left to the right.
So we have four, two, three,
four and two are less than five, we're good there,
three is less than six.
So that looks like a perfectly good binary heap.
And so this is where we're going to start our iteration.
So to run our algorithm in place,
rather than just popping things off the top of the heap,
we're going to do a swap.
So here, this is the value three
that would be orphaned if we were to remove nine, okay?
So what we're gonna do is we're gonna swap nine and three,
swap nine and three,
notice nine will go to the end of the vector
which is gonna become our sorted portion of the vector.
Three will swap with nine, that will appear at the root,
and then we're gonna have to restore
the heap order property.
So now we've swapped nine and three,
we've marked nine as sorted.
Notice that nine is no longer considered part of the heap,
but we have that problem, having three in the root position
as we do here violates the heap order property.
So we'll percolate this value down
until we find a suitable place for it.
And we'll do that by performing swaps.
Now, here, it's easy, we just have one step.
We swapped three with eight,
and that's gonna give us a binary heap.
So here we've swapped three and eight.
Now eight is in the root position.
Three is below eight, and below three are zero and one,
heap order property is intact.
And the next element that we're gonna remove
from the heap is eight.
So what are we gonna do with eight?
We're gonna swap it with two.
So now we've swapped eight and two,
and we mark eight as being sorted.
But now two is at the root,
and we need to restore the heap order property.
So again, we percolate down, choosing the larger element,
which one of these do we swap with?
Seven and three, we swap with the larger, okay?
So we're gonna swap seven and two.
Now we've swapped seven and two, do we have a heap yet?
No, why?
Because five and six are greater than two.
The heap order property is not intact.
So we're gonna swap
with the larger of those two, two and six.
So we swap two and six,
and now the heap order property is restored,
and seven is at the root.
Now, in the next iteration,
we're going to swap seven with four, seven and four, okay?
So we'll swap seven and four.
Now seven is sorted and four is at the root position.
Again, we need to restore the heap order property.
So we'll swap four and six,
and we'll need to swap one more time
to restore the heap order property.
We'll swap four and five.
And now we have three elements sorted,
seven, eight and nine,
and we've consumed the lowest level of our heap.
So to remove six and add it to our sorted portion,
we'll swap six and one.
I think you get the idea now,
so let's move through the rest a little more quickly.
We'll swap one and five.
We'll swap one and four,
and now we've restored the heap order property
and five is at the root.
Now we're gonna remove five by swapping it with zero.
Now, five has been swapped with zero, five is sorted.
Now we have five, six, seven, eight, nine sorted.
Zero is at the root,
so we have to restore the heap order property.
So we swap zero and four.
Now we swap zero and two,
and now we have a valid binary heap.
Now we're gonna remove four but from the heap
by swapping it with zero,
and zero percolates down by swapping with three.
We remove three by swapping with one.
Now we'll swap one and two
to restore the heap order property.
We're gonna remove two by swapping with zero.
Now we swap zero and one
to restore the heap order property.
Now we'll remove one, and now we've consumed our heap,
and our vector is sorted.
See, zero, one, two, three four,
five, six, seven, eight, nine.
And we're done.
Let's take a look at an animation
from the University of San Francisco website.
So now we're using the visualization tool
at University of San Francisco.
And you may be wondering what's going on here.
The first thing we need to do as you recall
is turn our vector into a binary heap.
And so what you see right now
is the preliminary work that's being done
in order to convert the original input vector
that we started with into a binary heap.
And then once that's done, it starts the process of sorting.
And so you see now that there are elements
accumulating on the right-hand side that are sorted,
and the process is identical
to what I just showed you earlier much more slowly.
We're removing the root element.
We're adding that to the sorted elements,
then we're percolating down
until we find a suitable home for our new root,
and thereby restore the heap order property.
Now, you may wonder what the time complexity is here,
and because the height of a binary tree
within elements is log n,
that means that the worst case
to restore the heap order property
is we're gonna need to perform log n swaps.
And we have to do that n times,
we have n elements we need to sort,
and in each case we could perform up to log n swaps.
And so that's how we get the time complexity
of o of n log n for this algorithm.
But you see this works
just the way we demonstrated in the slides,
just with a lot more numbers.
And now we're done, and we have this nice sorted vector.
Now, let's go back to our comparison chart.
Here we've added heap sort
among the algorithms that we've examined.
Heap sort has a time complexity of o of n log n,
that's the worst case and average case.
So unlike Quicksort, it doesn't have a worst case
of o of n squared,
it's guaranteed to perform an o of n log n time.
It has o of one space complexity, but it is not stable.
Unlike selection sort,
but the unsorted elements are in a heap.
And so that's where we get the performance boost
over selection sort.
So in summary,
heap sort is an improved selection sort
where we use a heap to manage our unsorted elements.
Heap sort has average case and worst case performance
of o of n log n, and heap sort is not stable.
And that wraps up our survey of sorting algorithms.
In the next presentation,
we will implement heap sort in C++,
and then we'll move on to new topics.