Course contentsShow
← Computer Science
Lesson 783 of 2,87218. Sorting AlgorithmsFree lesson

Heapsort Stability

Why heapsort is not a stable sorting algorithm and how heap operations can reorder equal elements.

Heapsort Stability

You'll learn: Why heapsort doesn't preserve the original order of equal elements, making it an unstable sorting algorithm.

What is Stability Again?

A stable sorting algorithm preserves the relative order of equal elements. If two items have the same key, whichever appeared first in the input will also appear first in the output. This property matters when sorting complex objects by one field while keeping their original order for ties.

Why Heapsort is Unstable

Heapsort performs two major operations that can scramble equal elements:

  1. Building the heap - When converting the array into a max-heap, elements are rearranged based on heap property rules, not their original positions. Equal elements may swap places during the "heapify" process.

  2. Extracting elements - During sorting, we repeatedly swap the root (largest element) with the last position in the unsorted portion. When multiple elements have the same value, which one becomes the root depends on heap structure, not their original input order.

A Simple Example

Imagine sorting these pairs by their first number: (3,A), (3,B), (3,C).

All three have equal keys. In a stable sort, the output would preserve order: (3,A), (3,B), (3,C).

With heapsort, the heap operations (parent-child comparisons and swaps) can easily produce (3,C), (3,A), (3,B) or any other permutation. The algorithm simply doesn't track or care about original positions—it only compares values.

Why This Happens

Heapsort's focus is on maintaining the heap property through swaps. When choosing between equal elements, there's no mechanism to favor the one that appeared earlier. The tree structure determines movement, not input order.

Key Takeaway: Heapsort is not stable because heap operations (building the heap and repeated swaps during extraction) reorder equal elements based on tree structure rather than preserving their original relative positions.