>> In this video we will use binary heaps to design the heap sort algorithm,

which is a fast and space efficient sorting algorithm.

In fact, using priority queues, or using binary heaps, it is not so difficult

to come up with an algorithm that sorts the given array in time of analog n.

Indeed, given a rate a of size m, we do the following.

First, just create an empty priority queue.

Then, insert all the elements from our array into our priority queue.

Then, extract the maximum one by one from the given array.

Namely, we first extract the maximum.

This is the maximum of our array, so put it to the last position.

Then, extract the next maximum and

put it to the left of the last position, and so on.

This clearly gives us a sorted array, right?

So, we know that if we use binary heaps as an implementation for

priority queue, then all operations work in logarithmic time.

So, this gives us an algorithm with a running time big o of n log n.

And recall that this is asymptotically optimal for

algorithms that are comparison-based.

And this algorithm is clearly comparison-based, all right?

Also, know that this is a natural generalization of selection

sort algorithm.

Recall that in selection sort algorithms, we proceed as follows.

Given an array, we first scan the whole array to find the maximum value.

So, then we get this maximum value and swap it with the last element.

Then, we forget about this last element and

we can see that only n-1 first elements.

Again, by scanning this array, we find the maximum value, and

we swap it with the last element in this region, and so on.

So, here in the heap sort algorithm,

instead of finding the maximum value at each iteration, namely,

we use a smart data structure, namely a binary heap, right?

So, the only disadvantage of our current algorithm

is that it uses additional space.

So, it uses additional space to store the priority queue.

Okay?

So, in this lesson we will show how to avoid this disadvantage.

Namely, given an array A, we will first permute its elements somehow,

so that the result in array is actually a binary heap.

So, it satisfies binary heap property.

And then, we will sort this array, again,

just by calling extract marks and minus one times.