Heapsort

Overview

Heapsort uses a max-heap to build a heap from an array and repeatedly extract the max element, producing a sorted array when finished.

Property	Value
Best Case	$O(n)$
Worst Case	$O(n\lg n)$
Avg. Case	$O(n\lg n)$
Aux. Memory	$O(1)$
Stable	No
Adaptive	Yes
Visualization

Loop Invariant

Heapsort has loop invariant $P$ given by

A[0:i-1] is a max-heap containing the i smallest elements of A. A[i:n-1] contains the n - i largest elements of A sorted.

We prove $P$ maintains the requisite properties:

• Initialization
  • A[0:n-1] is a max-heap and A[n:n-1] is empty.
• Maintenance
  • On each iteration, A[0] is swapped with A[i-1]. A[0] is originally the largest element of the max-heap and is smaller than the elements of A[i:n-1]. Thus A[i-1:n-1] is in sorted order. Decrementing i, decrementing the heap size, and invoking MAX_HEAPIFY_DOWN on A[0] fixes the max-heap property of A[0:i-1].
• Termination
  • We terminate when i = 1. Since A[0:1] is a max-heap, it follows A[0] < A[1]. Furthermore, A[2:n-1] are the largest n - 2 elements of A in sorted order. Thus A is sorted.