Heap Sort

Question 1

What is the "Heap Property" in a Max Heap?

Accepted Answer

Parent node >= Children nodes — In a Max Heap, for any given node I, the value of I is greater than or equal to the values of its children.

Question 2

What is heap sort's time complexity in all cases?

Accepted Answer

O(n log n) in every case — Building the heap is O(n) and each of n extractions costs O(log n), giving Θ(n log n) in every case — a guaranteed bound with no bad inputs.

Question 3

What is heap sort's auxiliary space complexity?

Accepted Answer

O(1) — Heap sort runs in place on the input array (the heap is built within it), using O(1) extra space — unlike merge sort's O(n) buffer.

Question 4

Is heap sort stable?

Accepted Answer

No; reheapification can reorder equal elements — Reheapification can reorder equal keys, so heap sort is not stable.

Question 5

To sort ASCENDING with heap sort, you typically use a…

Accepted Answer

Max-heap — Build a max-heap, swap the root (max) with the last element, shrink the heap, and sift down — producing ascending order from the back forward.

Question 6

In an array-based heap, the children of index i (0-indexed) are at…

Accepted Answer

2i+1 and 2i+2 — For 0-indexed arrays, left child = 2i+1, right child = 2i+2, and parent = (i−1)/2. This implicit structure needs no pointers.

Question 7

Building a heap from an arbitrary array via bottom-up heapify costs…

Accepted Answer

O(n) — Bottom-up build-heap is O(n): most nodes are near the leaves and sift down only a little; the cost sums to a geometric series bounded by O(n).

Question 8

The core operation that restores the heap property after removing the root is…

Accepted Answer

Sift-down — After placing a leaf at the root, sift-down swaps it with its larger child repeatedly until the max-heap property holds — O(log n).

Question 9

Why is heap sort chosen as the fallback inside introsort?

Accepted Answer

It guarantees O(n log n) worst-case time and O(1) space overhead — When quicksort's recursion gets too deep (risking O(n²)), introsort switches to heap sort for its guaranteed O(n log n) — a safety net.

Question 10

Heap sort's main practical drawback versus quicksort is…

Accepted Answer

Poor cache locality from non-sequential parent-child index jumps — Parent/child accesses jump by powers of two across memory, causing cache misses; quicksort's sequential scans are more cache-friendly, so quicksort is usually faster despite equal asymptotics.

Heap Sort

Sort with a heap

Test your knowledge

What is the "Heap Property" in a Max Heap?

The short version

In more depth

Structure from Chaos

Why use it?

When to reach for this

Interview Questions

References & Further Reading

Love this visualization?