Loading algorithms…

Loading visualizer…

Algorithms/Sorting/Heap Sort

Heap Sort

Sort in-place using a max-heap. Phase 1 builds the heap; phase 2 repeatedly extracts the max. Guaranteed O(n log n) with no extra memory.

SortingHeapIn-PlaceO(n log n)Not Stable
Comparisonsso far
0
Writesso far
0

Heap + Array View

The bar chart and the binary tree are the same data — the array is the heap's level-order storage.

default active comparing swapping sorted
Array (level-order)in-place · O(1) extra
Arrayn = 16
10
21
32
43
54
65
76
87
98
109
1110
1211
1312
1413
1514
1615
Heap (binary tree)parent(i) = ⌊(i-1)/2⌋
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
1 / 0
Speed
Preset
n16
heap-sort.js
1function heapSort(arr) {
2 const n = arr.length;
3 
4 // PHASE 1: build a max-heap in-place
5 for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
6 siftDown(arr, i, n);
7 }
8 
9 // PHASE 2: repeatedly extract the max
10 for (let end = n - 1; end > 0; end--) {
11 swap(arr, 0, end); // move max to the end
12 siftDown(arr, 0, end); // restore heap on [0..end-1]
13 }
14}
15 
16function siftDown(arr, root, n) {
17 while (true) {
18 const left = 2 * root + 1;
19 const right = 2 * root + 2;
20 let largest = root;
21 
22 if (left < n && arr[left] > arr[largest]) largest = left;
23 if (right < n && arr[right] > arr[largest]) largest = right;
24 if (largest === root) break; // heap property restored
25 
26 swap(arr, root, largest); // bubble root down
27 root = largest; // continue sifting
28 }
29}

Algorithm Explanation

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure. It runs in two phases: first it builds a max-heap from the input array, then it repeatedly extracts the maximum and shrinks the heap. Invented by J. W. J. Williams in 1964, it's the canonical in-place O(n log n) sort.

⚙️ How It Works

  1. Build a max-heap on the entire array. A max-heap is a complete binary tree where every parent is ≥ its children — so the largest element sits at the root, index 0. We build it in O(n) by sifting down from the last internal node.
  2. Extract the max: swap the root arr[0] with the last element of the heap, then shrink the heap by one. The element we just moved to the end is now in its final sorted position.
  3. Restore the heap by sifting down the new root. The heap property may be violated locally — sift down the larger child until the heap is valid.
  4. Repeat until the heap has size 1. Each iteration locks one element into its final position, so the sorted suffix grows from the right.

🌳 The Implicit Heap

A binary heap can be stored in a plain array using level-order traversal:

parent(i) = ⌊(i − 1) / 2⌋
left(i) = 2i + 1
right(i) = 2i + 2

No pointers, no auxiliary buffer — the heap lives entirely inside the input array. This is what makes heap sort truly in-place.

💡 Time complexity: Build heap is O(n) (not O(n log n) — most nodes sift down only a few levels). Each of the n − 1 extract operations does O(log n) work. Total: O(n log n). And unlike quicksort, it's guaranteed— no O(n²) worst case.

⚖️ Heap vs Merge vs Quick

Merge sort
  • Guaranteed O(n log n).
  • Stable — preserves order of equals.
  • Needs O(n) extra buffer.
  • Great for linked lists & external sort.
Quick sort
  • O(n log n) average, O(n²) worst case.
  • Not stable by default.
  • In-place (O(log n) stack).
  • Faster in practice on random data due to cache locality.
Heap sort (this page)
  • Guaranteed O(n log n).
  • Not stable.
  • In-place (O(1) extra).
  • Worse cache behaviour than quick / merge sort.
←Previous Algorithm
Quick Sort
SortingO(n log n) avg
Next Algorithm→
Bubble Sort
O(n²)Sorting

The tree view shows the implicit-binary-heap layout: index 0 is the root, indices 1 & 2 are the root's children, and so on.