Course contentsShow
← Computer Science
Lesson 606 of 2,87214. Heaps and Priority QueuesFree lesson

Heapsort Space Complexity and Stability

Understanding heapsort's O(1) space complexity and why it is not a stable sorting algorithm.

Heapsort Space Complexity and Stability

You'll learn why heapsort is space-efficient but doesn't preserve the original order of equal elements.

Space Complexity: O(1) Extra Space

Heapsort operates in-place, meaning it sorts the array without requiring additional arrays or data structures proportional to the input size. The array itself is rearranged to form a heap, and the sorting happens by swapping elements within that same array.

Why O(1)? You only need a constant amount of extra memory for variables like loop counters and temporary swap storage. No matter how large your input array grows, the extra space remains fixed.

Analogy: Imagine sorting books on a shelf by rearranging them directly on that shelf, rather than moving them to a second shelf. You might hold one book temporarily in your hands (constant space), but you don't need a whole second shelf.

Stability: Heapsort is NOT Stable

A sorting algorithm is stable if it preserves the relative order of equal elements. For example, if two items have the same priority but appeared in a specific order originally, a stable sort keeps that order.

Why heapsort is unstable: During the heapify-down operations and extract-max phase, elements are moved based solely on their values, not their original positions. Equal elements can leapfrog each other during these swaps, breaking their original order.

Example: Sorting [(5, "first"), (3, "x"), (5, "second")] by the number might produce [(3, "x"), (5, "second"), (5, "first")] — notice the two 5s swapped positions.

If you need stability, consider merge sort or insertion sort instead.

Key Takeaway: Heapsort achieves O(1) extra space complexity by sorting in-place, but it is not a stable sorting algorithm because heap operations can rearrange equal elements unpredictably.