# 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 $a[0],...,a[n − 1]$ 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 $a[0],...,a[n − 2]$ once again are a valid heap representation. When
this process ends (because $n = 0$) 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)`

.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy