Heap Sort Visualizer: Step-by-Step Animation & Complexity

Heap Sort

Category: Sorting | Time: O(n log n) | Space: O(1)

Input Data

Visualization

Visual representation of the data structure

About Heap Sort

A comparison-based sorting technique based on a Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for the remaining elements.

Code Editor

The code is for reference. Editing it won't affect the visualization.

function heapSort(arr) {
    var n = arr.length;
    for (var i = Math.floor(n / 2) - 1; i >= 0; i--)
        heapify(arr, n, i);
    for (var i = n - 1; i > 0; i--) {
        var temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
    return arr;
}
function heapify(arr, n, i) {
    var largest = i;
    var l = 2 * i + 1;
    var r = 2 * i + 2;
    if (l < n && arr[l] > arr[largest])
        largest = l;
    if (r < n && arr[r] > arr[largest])
        largest = r;
    if (largest != i) {
        var swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;
        heapify(arr, n, largest);
    }
}

Variable State

{
  "arr": "[12, 11, 13, 5, 6, 7]",
  "n": 6
}

Heap Sort: How It Works

Last updated October 28, 2026

Overview

Heap Sort first rearranges the array into a max-heap: a complete binary tree stored in the array where every parent is at least as large as its children. For index i, the children live at 2i + 1 and 2i + 2, so no pointers are needed.

Once the heap is built, the largest value is at index 0. Heap Sort swaps it to the end of the array, shrinks the heap by one, and calls heapify to sink the new root to its proper level. Repeating this extracts values from largest to smallest, filling the array from the back.

With the default input 12, 11, 13, 5, 6, 7, building the heap moves 13 to the root. Each extraction then fixes one more value at the end — 13, then 12, then 11 — until the array is sorted.

Step by step

Build a max-heap by calling heapify on every non-leaf node from n/2 - 1 down to 0.
Swap the root (the maximum) with the last element of the heap.
Reduce the heap size by one; the swapped-out maximum is now in its final place.
Call heapify on the root to restore the heap property.
Repeat until the heap has one element.

Complexity

Case	Cost	Why
Best case	O(n log n)	Every extraction sifts a value down up to log n levels.
Average case	O(n log n)	n extractions at O(log n) each.
Worst case	O(n log n)	Guaranteed; building the heap itself is only O(n).
Extra space	O(1)	The heap lives inside the input array.

When to use it

When you need a worst-case O(n log n) sort with no extra memory, e.g. embedded or real-time systems.
As the safety net inside Intro Sort when Quick Sort recursion gets too deep.
When you only need the top k elements: stop after k extractions.

Common mistakes

It is not stable, and its jumps across the array make it noticeably slower than Quick Sort on real hardware because of cache misses.
Off-by-one mistakes in the child formulas (2i / 2i + 1 belong to 1-based heaps, not 0-based arrays).
Forgetting to pass the shrinking heap size to heapify, which drags already-sorted values back into the heap.

Worked Example: Heap Sort Dry Run

Generated from the same trace that drives the visualizer above, using the default input.

A dry run is the best way to check your understanding of Heap Sort: follow each row, predict the next one, and compare. The run below takes 146 steps in total. Steps that only re-print loop counters are left out so the decisions stand out. The Line column refers to the line numbers in the code listing above.

Input: 12, 11, 13, 5, 6, 7
Result: arr = [5, 6, 7, 11, 12, 13], return value = [5, 6, 7, 11, 12, 13]

Step	Line	Array	What happens
1	2	[12, 11, 13, 5, 6, 7]	n = 6
7	18	[12, 11, 13, 5, 6, 7]	n = 6, i = 2, largest = 2, l = 5, r = 6, condition = 5 < 6 && 7 > 13
8	20	[12, 11, 13, 5, 6, 7]	n = 6, i = 2, largest = 2, l = 5, r = 6, condition = 6 < 6 && undefined > 13
9	22	[12, 11, 13, 5, 6, 7]	n = 6, i = 2, largest = 2, condition = 2 != 2
16	18	[12, 11, 13, 5, 6, 7]	n = 6, i = 1, largest = 1, l = 3, r = 4, condition = 3 < 6 && 5 > 11
17	20	[12, 11, 13, 5, 6, 7]	n = 6, i = 1, largest = 1, l = 3, r = 4, condition = 4 < 6 && 6 > 11
18	22	[12, 11, 13, 5, 6, 7]	n = 6, i = 1, largest = 1, condition = 1 != 1
25	18	[12, 11, 13, 5, 6, 7]	n = 6, i = 0, largest = 0, l = 1, r = 2, condition = 1 < 6 && 11 > 12
26	20	[12, 11, 13, 5, 6, 7]	n = 6, i = 0, largest = 0, l = 1, r = 2, condition = 2 < 6 && 13 > 12
28	22	[12, 11, 13, 5, 6, 7]	n = 6, i = 0, largest = 2, condition = 2 != 0
30	24	[13, 11, 13, 5, 6, 7]	n = 6, i = 0, largest = 2, arr[i] = 13
31	25	[13, 11, 12, 5, 6, 7]	n = 6, i = 0, largest = 2, arr[largest] = 12
36	18	[13, 11, 12, 5, 6, 7]	n = 6, i = 2, largest = 2, l = 5, r = 6, condition = 5 < 6 && 7 > 12
37	20	[13, 11, 12, 5, 6, 7]	n = 6, i = 2, largest = 2, l = 5, r = 6, condition = 6 < 6 && undefined > 12
38	22	[13, 11, 12, 5, 6, 7]	n = 6, i = 2, largest = 2, condition = 2 != 2
42	7	[7, 11, 12, 5, 6, 7]	n = 6, i = 5, temp = 13, arr[0] = 7
43	8	[7, 11, 12, 5, 6, 13]	n = 6, i = 5, temp = 13, arr[i] = 13
48	18	[7, 11, 12, 5, 6, 13]	n = 5, i = 0, largest = 0, l = 1, r = 2, condition = 1 < 5 && 11 > 7
50	20	[7, 11, 12, 5, 6, 13]	n = 5, i = 0, largest = 1, l = 1, r = 2, condition = 2 < 5 && 12 > 11
52	22	[7, 11, 12, 5, 6, 13]	n = 5, i = 0, largest = 2, condition = 2 != 0
54	24	[12, 11, 12, 5, 6, 13]	n = 5, i = 0, largest = 2, arr[i] = 12
55	25	[12, 11, 7, 5, 6, 13]	n = 5, i = 0, largest = 2, arr[largest] = 7
60	18	[12, 11, 7, 5, 6, 13]	n = 5, i = 2, largest = 2, l = 5, r = 6, condition = 5 < 5 && 13 > 7
61	20	[12, 11, 7, 5, 6, 13]	n = 5, i = 2, largest = 2, l = 5, r = 6, condition = 6 < 5 && undefined > 7
62	22	[12, 11, 7, 5, 6, 13]	n = 5, i = 2, largest = 2, condition = 2 != 2
66	7	[6, 11, 7, 5, 6, 13]	n = 6, i = 4, temp = 12, arr[0] = 6
67	8	[6, 11, 7, 5, 12, 13]	n = 6, i = 4, temp = 12, arr[i] = 12
72	18	[6, 11, 7, 5, 12, 13]	n = 4, i = 0, largest = 0, l = 1, r = 2, condition = 1 < 4 && 11 > 6
74	20	[6, 11, 7, 5, 12, 13]	n = 4, i = 0, largest = 1, l = 1, r = 2, condition = 2 < 4 && 7 > 11
75	22	[6, 11, 7, 5, 12, 13]	n = 4, i = 0, largest = 1, condition = 1 != 0
77	24	[11, 11, 7, 5, 12, 13]	n = 4, i = 0, largest = 1, arr[i] = 11
78	25	[11, 6, 7, 5, 12, 13]	n = 4, i = 0, largest = 1, arr[largest] = 6
83	18	[11, 6, 7, 5, 12, 13]	n = 4, i = 1, largest = 1, l = 3, r = 4, condition = 3 < 4 && 5 > 6
84	20	[11, 6, 7, 5, 12, 13]	n = 4, i = 1, largest = 1, l = 3, r = 4, condition = 4 < 4 && 12 > 6
85	22	[11, 6, 7, 5, 12, 13]	n = 4, i = 1, largest = 1, condition = 1 != 1
89	7	[5, 6, 7, 5, 12, 13]	n = 6, i = 3, temp = 11, arr[0] = 5
90	8	[5, 6, 7, 11, 12, 13]	n = 6, i = 3, temp = 11, arr[i] = 11
95	18	[5, 6, 7, 11, 12, 13]	n = 3, i = 0, largest = 0, l = 1, r = 2, condition = 1 < 3 && 6 > 5
97	20	[5, 6, 7, 11, 12, 13]	n = 3, i = 0, largest = 1, l = 1, r = 2, condition = 2 < 3 && 7 > 6
99	22	[5, 6, 7, 11, 12, 13]	n = 3, i = 0, largest = 2, condition = 2 != 0

The remaining 21 key steps follow the same pattern. Press play in the visualizer to watch every step through to the result.

Frequently Asked Questions

About Heap Sort

What is Heap Sort?

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It divides the input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region.

How does Heap Sort build the initial heap?

It starts from the last non-leaf node of the tree (at index n/2 - 1) and calls a 'heapify' function on each node up to the root. The heapify function ensures that the subtree rooted at a given node maintains the max-heap property.

What is the time complexity of Heap Sort?

Heap Sort has a reliable time complexity of O(n log n) for all cases (best, average, and worst). Building the initial heap takes O(n), and each of the n extractions takes O(log n).

What is the space complexity of Heap Sort?

Heap Sort is an in-place algorithm with a space complexity of O(1). It sorts the array by rearranging elements within the array itself.

Is Heap Sort stable?

No, Heap Sort is not a stable algorithm. The process of heapifying and swapping elements can change the relative order of items with equal values.

What is a 'heapify' operation?

Heapify (also known as 'sift-down' or 'max-heapify') is the process of restoring the heap property at a single node. It assumes the subtrees of the node are already heaps. It compares the node with its children and swaps with the larger child if necessary, then recursively calls itself on the affected subtree.

How does Heap Sort compare to Quick Sort?

Heap Sort has a better worst-case time complexity (O(n log n)) than Quick Sort (O(n^2)). However, Quick Sort is often faster in practice due to better cache locality and fewer comparisons on average.

Is Heap Sort a good choice for sorting linked lists?

No, Heap Sort relies heavily on random access to elements (e.g., finding a parent or child at `arr[i]` and `arr[2i+1]`), which is very inefficient in a linked list. It is best suited for arrays.

What is the main sorting logic after the heap is built?

After the max-heap is built, the largest element is always at the root (index 0). The algorithm swaps the root with the last element of the heap, effectively moving the largest element to its final sorted position. It then reduces the heap's size by one and calls 'heapify' on the new root to restore the heap property.

What are the main use cases for Heap Sort?

Heap Sort is useful when a guaranteed O(n log n) worst-case performance is needed and when space is limited (since it's in-place). It is also the underlying algorithm for a Priority Queue data structure.

Where can I learn more?

You can find a more detailed explanation on GeeksforGeeks.