How does Heap Sort work?

Heap Sort works by first building a Max-Heap from the input data, then repeatedly swapping the root (largest element) with the last unsorted element and rebuilding the heap.

No, Heap Sort is not a stable sorting algorithm because the heap construction and extraction processes can swap equal elements across large distances.

Heap Sort vs Merge Sort?

Both are O(n log n), but Heap Sort works in-place (O(1) extra space), while Merge Sort is stable and often faster for linked lists.

Heap Sort

Heap sort is a selection-based sorting algorithm that uses a binary heap to find the maximum element efficiently.

Intuition

Imagine a corporate hierarchy where the boss (largest number) must always be at the top. We repeatedly remove the boss, send them to retirement (sorted end), and promote a new boss, adjusting the hierarchy until everyone is retired (sorted).

Concept

Max Heap: A binary tree where Parent >= Children. Root is always the Max.
Heapify: The process of restoring the heap property after the root changes.
In-Place: Uses the same array to store the heap and the sorted result.

How it Works

Algorithm:

Build a Max Heap from the input array.
Swap the Root (Max) with the last element.
Reduce heap size by 1 (the last element is now sorted).
Heapify the new Root to restore Max Heap property.

Step-by-Step Breakdown

Watch the visualization:

Blue bar (NODE): The subtree root being sifted down.
Amber bars: The parent and child being compared.
Red bars: A swap: fixing the heap property, or moving the max to the end.
Green bars: Sorted elements at the end of the array.

When to Use

Guaranteed O(N log N): Good worst-case performance unlike Quick Sort.
Space Constraints: O(1) extra space.
Priority Queues: Excellent for finding the 'Top K' items.

When NOT to Use

Cache Performance: Poor locality of reference compared to Quick Sort.
Stable Sort Required: It is unstable.

How to Identify

"Top K Elements", "Priority Queue", "Heaps".

Sample Problems

Kth Largest Element (LeetCode 215)

Classic application of Heap.

Merge K Sorted Lists

Essential usage of Min-Heap.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description

Quick Sort

Shell Sort

Complexity

Time (Best)

O(N log N)

Time (Average)

O(N log N)

Time (Worst)

O(N log N)

Space

O(1)

Heap Sort Code

1function heapSort(arr) {
2    let n = arr.length;
3    for (let i = Math.floor(n / 2) - 1; i >= 0; i--)
4        heapify(arr, n, i);
5    for (let i = n - 1; i > 0; i--) {
6        [arr[0], arr[i]] = [arr[i], arr[0]];
7        heapify(arr, i, 0);
8    }
9    return arr;
10}
11
12function heapify(arr, n, i) {
13    let largest = i;
14    let l = 2 * i + 1;
15    let r = 2 * i + 2;
16    if (l < n && arr[l] > arr[largest]) largest = l;
17    if (r < n && arr[r] > arr[largest]) largest = r;
18    if (largest !== i) {
19        [arr[i], arr[largest]] = [arr[largest], arr[i]];
20        heapify(arr, n, largest);
21    }
22}

Related Lessons

Heap Sort

Intuition

Concept

How it Works

Step-by-Step Breakdown

When to Use

When NOT to Use

How to Identify

Sample Problems

Kth Largest Element (LeetCode 215)

Merge K Sorted Lists

AI resume checker — match your resume to the job description

Bubble Sort

Selection Sort

Insertion Sort

Merge Sort

Frequently Asked Questions

How does Heap Sort work?

Is Heap Sort stable?

Heap Sort vs Merge Sort?