Heap-sort
Learn about heap-sort through its visual demonstration.
We'll cover the following...
The heap-sort algorithm is another in-place sorting algorithm. Heap-sort
uses the binary heaps we discussed before. Recall that the BinaryHeap
data structure represents a heap using a single array. The heap-sort algorithm converts the input array a
into a heap and then repeatedly extracts the minimum value.
More specifically, a heap stores n
elements in an array, a
, at array locations with the smallest value stored at the root, a[0]
. After transforming a
into a BinaryHeap
, the heap-sort algorithm repeatedly swaps a[0]
and a[n − 1]
, decrements n
, and calls trickleDown(0)
so that once again are a valid heap representation. When
this process ends (because ) the elements of a
are stored in decreasing order, so a
is reversed to obtain the final sorted order.
Note: The algorithm could alternatively redefine the
compare(x, y)
function so that the heap-sort algorithm stores the elements directly in ascending order.
Visual demonstration
The figure below shows an example of the execution of heapSort(a)
.
A snapshot of the execution of heapSort(a)
. The shaded part of the array
is already sorted. The unshaded part is a BinaryHeap
. During the next iteration, element 5 will be placed into array
location 8.
void sort(array<T> &b) {BinaryHeap<T> h(b);while (h.n > 1) {h.a.swap(--h.n, 0);h.trickleDown(0);}b = h.a;b.reverse();}
Heap-sort subroutines
A key subroutine in heap-sort is the constructor for turning an unsorted array a
into a heap. It would be easy to do this in time by
repeatedly calling the BinaryHeap
add(x)
method, but we can do better by
using a bottom-up algorithm. Recall that, in a binary heap, the children
of a[i]
are stored at positions a[2i + 1]
and a[2i + 2]
. This implies that the elements ...
Create a free account to access the full course.
By signing up, you agree to Educative's Terms of Service and Privacy Policy