How Does Heapsort Use an Implicit Binary Heap to Sort?

Heapsort is a comparison-based sorting algorithm that organizes an input array into an implicit binary heap to sort elements in place. By treating the flat array as a complete binary tree using simple index arithmetic, the algorithm avoids allocating extra memory for pointers or auxiliary arrays. It first transforms the unsorted array into a max-heap and then repeatedly extracts the maximum element to build the sorted sequence from the end of the array backward, achieving worst-case logarithmic-linear time complexity and constant auxiliary space.

The Implicit Binary Heap Structure

An implicit binary heap stores a complete binary tree inside a standard contiguous array \(A\) of length \(n\) without explicit node pointers. For any element at zero-based index \(i\), its tree relationships are computed directly:

  • Parent index: \(\lfloor (i - 1) / 2 \rfloor\)
  • Left child index: \(2i + 1\)
  • Right child index: \(2i + 2\)

Because the tree is complete, every level is filled except possibly the last, which is filled from left to right. This guarantees that the height of the tree is \(\lfloor \log_2 n \rfloor\). For sorting in ascending order, Heapsort uses a max-heap, where every node satisfies the max-heap property:

\[A[\text{parent}(i)] \ge A[i]\]

This invariant ensures that the largest element in the heap always resides at the root, \(A[0]\).

Phase 1: Building the Max-Heap

Before sorting can begin, the arbitrary input array must be rearranged into a valid max-heap. A naive approach of inserting elements one by one takes \(O(n \log n)\) time, but Floyd's bottom-up heap construction algorithm accomplishes this in \(O(n)\) time.

All elements at indices \(\lfloor n / 2 \rfloor\) through \(n - 1\) are leaves of the binary tree, so each trivially satisfies the max-heap property. The algorithm iterates backward from index \(\lfloor n / 2 \rfloor - 1\) down to \(0\), calling a siftDown (or heapify) procedure on each node. The siftDown operation compares a node with its children and swaps it with the larger child if the max-heap property is violated, repeating this downward until the element settles into a valid position.

Although each siftDown call takes \(O(\log n)\) time in the worst case, most nodes are near the bottom of the tree and travel only a short distance. Summing the work across all levels yields a linear bound:

\[\sum_{h=0}^{\lfloor \log_2 n \rfloor} \left\lceil \frac{n}{2^{h+1}} \right\rceil O(h) = O(n)\]

Phase 2: Iterative Extraction and Sorting

Once the max-heap is built, the largest element is at \(A[0]\). Heapsort sorts the array in place by partitioning it into a shrinking heap prefix \(A[0 \dots k]\) and a growing sorted suffix \(A[k+1 \dots n-1]\).

For \(k\) from \(n - 1\) down to \(1\):

  1. Swap the root \(A[0]\) with the last element of the current heap, \(A[k]\).
  2. Decrement the logical heap size to \(k\), locking the newly placed maximum at \(A[k]\) in its final sorted position.
  3. Call siftDown on the new root \(A[0]\) within the reduced heap \(A[0 \dots k-1]\) to restore the max-heap property.

Each of the \(n - 1\) extractions performs one swap in \(O(1)\) time and one siftDown operation over a heap of height at most \(\lfloor \log_2 k \rfloor\), taking \(O(\log n)\) time. Therefore, the extraction phase takes \(O(n \log n)\) time in both the average and worst cases.

Time and Space Complexity

Combining both phases gives a total worst-case, average-case, and best-case (for distinct elements) time complexity of:

\[T(n) = O(n) + O(n \log n) = O(n \log n)\]

Because all swaps and siftDown operations occur directly within the input array using only a fixed number of index and temporary swap variables, the iterative implementation requires \(O(1)\) auxiliary space. Unlike Quicksort, which can degrade to \(O(n^2)\) time on adversarial inputs, or Mergesort, which requires \(O(n)\) extra space for standard array implementations, Heapsort guarantees \(O(n \log n)\) time with strictly constant auxiliary memory.