Heap-sort

Learn about heap-sort through its visual demonstration.

The heap-sort algorithm is another in-place sorting algorithm. Heap-sort uses the binary heaps. 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 nn 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=0n = 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 a snapshot of the execution of heapSort(a, c). 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.

Create a free account to access the full course.

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