Sorting Tested code in 3 languages

Heap Sort, Visualized as a Tree and an Array

Turn the array into a max-heap, swap the biggest value to the end, repair the heap, repeat. Press play to watch the same numbers as a binary tree and as bars, next to the exact line of code that runs.

Crio.Do · Last updated 19 November 2026

Interactive heap sort

Sort indices 0–7 (8 values). Read the array as a binary tree: the children of index i are 2i + 1 and 2i + 2. Phase 1 turns it into a max-heap, where every parent is at least as big as its children.

0Comparisons
0Swaps
1/–Step
def heap_sort(a):    n = len(a)    for i in range(n // 2 - 1, -1, -1):        sift_down(a, i, n)    for end in range(n - 1, 0, -1):        a[0], a[end] = a[end], a[0]        sift_down(a, 0, end)  def sift_down(a, i, size):    while True:        largest = i        left, right = 2 * i + 1, 2 * i + 2        if left < size and a[left] > a[largest]:            largest = left        if right < size and a[right] > a[largest]:            largest = right        if largest == i:            return        a[i], a[largest] = a[largest], a[i]        i = largest

The highlighted line is the one the animation is running. This is the exact code we test.

Tip: use the arrow keys to step when the visualizer has focus. Try duplicates, a sorted list or your own numbers.

On this page
  1. How it works
  2. Worked example
  3. Complexity
  4. When to use it
  5. Common mistakes
  6. Interview questions
  7. FAQ
  8. Sources

How heap sort works

Heap sort never builds a tree out of pointers. It reads the array itself as a binary tree: index 0 is the root, and the children of index i are 2i + 1 and 2i + 2. That is why the visualizer draws the same numbers twice, as a tree on top and as bars below. A swap in one is the same swap in the other.

A max-heap is that tree with one rule: every parent is at least as big as its children. Nothing else is ordered, but the rule forces the largest value to the root. Think of an office hierarchy where every manager outranks their own team: the top person outranks everyone, even though two teams are never compared directly.

Phase 1 builds the heap bottom-up. Leaves are already tiny heaps, so it starts at the last parent, n/2 − 1, and walks back to the root. At each parent it calls sift_down: compare the value with its children and, if a child is bigger, swap with the bigger child and keep going down. This phase costs O(n), not O(n log n), because most nodes sit near the bottom and can only fall a level or two.

Phase 2 sorts. The root is the largest value, so swap it with the last value of the heap. That value is now in its final place, and the heap shrinks by one. The value that landed on the root is usually small, so sift it down to repair the heap. After n − 1 rounds the array is sorted. Each repair costs at most one walk from root to leaf, about log₂ n levels, which gives O(n log n) in every case.

The algorithm in 5 steps

  1. 1 Read the array as a tree: the children of index i are 2i + 1 and 2i + 2.
  2. 2 For every parent from n/2 − 1 down to 0, sift its value down: swap it with its bigger child until neither child is bigger. The array is now a max-heap.
  3. 3 Swap the root, the largest value in the heap, with the last value in the heap. That index is now final.
  4. 4 Shrink the heap by one and sift the new root down to restore the heap rule.
  5. 5 Repeat steps 3 and 4 until the heap holds one value. The array is sorted.

Worked example

Here is the full run on a fixed array, generated by the same code as the visualizer. The first row is the end of phase 1, when the array has become a max-heap. Each row after that is one root swap: the largest value left goes to its final place. The sift-down steps in between are counted in the total but not listed.

Input: [12, 31, 7, 25, 18, 3]

  1. Step 17 Phase 1 done: the array is a max-heap, so the largest value, 31, is at the root (index 0). Phase 2: swap the root to the end, shrink the heap by one, repair it, repeat. 3125712183
  2. Step 18 Swap the root 31 (the largest value left) with 3 at index 5. 31 is now final at index 5; the heap shrinks to indices 0–4. 3257121831
  3. Step 26 Swap the root 25 (the largest value left) with 3 at index 4. 25 is now final at index 4; the heap shrinks to indices 0–3. 3187122531
  4. Step 33 Swap the root 18 (the largest value left) with 3 at index 3. 18 is now final at index 3; the heap shrinks to indices 0–2. 3127182531
  5. Step 38 Swap the root 12 (the largest value left) with 7 at index 2. 12 is now final at index 2; the heap shrinks to indices 0–1. 7312182531
  6. Step 41 Swap the root 7 with 3 at index 1. 7 is final at index 1, and 3, the smallest value, is left at index 0: sorted. 3712182531

Total for this run: 17 comparisons and 12 swaps, in 42 animation steps. Result: 3, 7, 12, 18, 25, 31.

Time and space complexity

Best

O(n log n)

With distinct values, every root swap brings a small value to the top that must sift back down. Even sorted input pays the full cost. Only an array where every value is equal finishes in O(n).

Average

O(n log n)

n − 1 repairs, each walking at most log₂ n levels with two comparisons per level, plus an O(n) build.

Worst

O(n log n)

No input can make it quadratic. Sedgewick and Wayne bound it at under 2n log₂ n + 2n comparisons.

Space

O(1)

The heap lives inside the array. The sift-down here is a loop, so there is no recursion stack either.

Stable:
No
In place:
Yes
Adaptive:
No
Worst case:
O(n log n)

Six sorts, same 8 numbers

Comparison counts from running each algorithm on the visualizer's array, then on the same numbers already sorted and in reverse order. Computed from the code on these pages, not typed in.

AlgorithmComparisonsMovesSorted inputReversed input
Insertion sort 1713 shifts728
Selection sort 285 swaps2828
Bubble sort 2513 swaps728
Merge sort 1624 writes1212
Quick sort 385 swaps3132
Heap sort 2619 swaps2724

The last two columns are comparisons too. Exact counts depend on the input and the variant (this page's heap sort builds its heap bottom-up and counts both child comparisons on every level of a sift), which is why complexity is stated as growth, not exact numbers.

When to use it, and when not to

Good fit

  • You need a guaranteed O(n log n) with no extra memory. The Linux kernel's generic sort() in lib/sort.c is a heapsort for exactly this reason: its comments say quicksort's O(n²) worst case can be exploited and its extra memory needs suit the kernel less.
  • As a safety net inside a faster sort. GCC's std::sort is an introsort: it runs quick sort, and if the recursion goes deeper than 2·log₂ n it switches that part to heap sort, so the worst case stays O(n log n).
  • You only need the top k values in order: build the heap in O(n), then stop after k root swaps, O(n + k log n) in total.
  • Learning priority queues: the same sift-down and the same index arithmetic run Python's heapq, Java's PriorityQueue and every scheduler built on a binary heap.

Pick something else when

  • You need a stable sort, for example sorting records by a second key after a first. Use merge sort or your language's built-in stable sort.
  • Raw speed on large arrays of numbers. A well-tuned quick sort usually wins in practice: it makes fewer comparisons on average and reads memory in order, while heap sort jumps from index i to 2i + 1 and misses the CPU cache.
  • Nearly sorted data. Heap sort does the same O(n log n) work anyway, while insertion sort or Timsort finish in close to O(n).
  • Linked lists. Finding the children of a node needs indexing by position, which a linked list cannot do in O(1). Merge sort is the natural fit.

Common mistakes and bugs

  1. 1.Using 1-based child formulas on a 0-based array

    Textbooks that start the heap at index 1 use children 2i and 2i + 1, parent i // 2. In a 0-based array that makes index 0 its own child. With index 0 as the root, the children are 2i + 1 and 2i + 2 and the parent is (i − 1) // 2.

  2. 2.Building the heap from the root downwards

    Sift-down only works when both subtrees are already heaps, so the build loop must run from the last parent back to 0. Running it from 0 forwards fails: on [1, 2, 3, 4] it produces [3, 4, 1, 2], where the root 3 is smaller than its child 4.

  3. 3.Forgetting to shrink the heap

    After swapping the root to index end, call sift_down(a, 0, end), not sift_down(a, 0, n). With the full size, the sift can pull the values you just put in their final places back into the heap.

  4. 4.Swapping with the left child by default

    The parent must swap with the bigger child. Swapping with the left one when the right one is bigger puts a smaller value above the right child and breaks the heap rule. Compare both children first, then swap once.

  5. 5.Using a min-heap to sort ascending in place

    A min-heap puts the smallest value at the root, and swapping it to the end of the array builds the result in descending order. For ascending order in place, use a max-heap. Popping a min-heap into a new list also works, but it needs O(n) extra space.

Interview questions

Try answering before you open the model answer.

Q1 Why does building a heap take O(n) and not O(n log n)?

Model answer: Sift-down costs at most the height of the node, and most nodes are low. Half the nodes are leaves and cost nothing, a quarter can fall one level, an eighth two, and so on. The total, n/4 · 1 + n/8 · 2 + n/16 · 3 + ..., stays below n swaps, and Sedgewick and Wayne bound the comparisons at under 2n.

Q2 Heap sort is O(n log n) in the worst case and quick sort is not. Why is quick sort usually preferred?

Model answer: Quick sort makes about 1.39 n log₂ n comparisons on average, heap sort close to 2 n log₂ n. Quick sort also scans memory in order, while heap sort jumps from i to 2i + 1, which misses the cache on large arrays. Libraries get both: introsort runs quick sort and falls back to heap sort if recursion gets too deep.

Q3 Why is heap sort not stable? Show an example.

Model answer: Root swaps move values across long distances. Take [5, 5, 2] and call the 5s A and B. The array is already a heap. Swapping the root puts A last: [2, B, A]. Sifting 2 down gives [B, 2, A], and the next root swap gives [2, B, A]. The two 5s finish in reverse order.

Q4 Find the k largest values in an array of n values.

Model answer: Keep a min-heap of size k: push each value, and once the heap holds more than k values pop the smallest. That is O(n log k) time and O(k) space, and it works on a stream. If the whole array is in memory, heapify it as a max-heap in O(n) and pop k times, O(n + k log n).

Q5 How is heap sort related to selection sort?

Model answer: Both repeatedly take the extreme value of the unsorted part and put it in its final place. Selection sort finds it by scanning, O(n) per pass, O(n²) in total. Heap sort keeps the unsorted part as a max-heap, so the largest value is always at the root and each repair is O(log n), O(n log n) in total.

Frequently asked questions

What is the time complexity of heap sort?

O(n log n) in the best, average and worst case, with O(1) extra space. Building the max-heap takes O(n). Each of the n − 1 root swaps is followed by a sift-down of at most log₂ n levels. Unlike quick sort, no input can make it quadratic; only an array of all-equal values finishes in O(n).

Is heap sort stable?

No. Swapping the root with the last value of the heap moves values over long distances, so equal values can change order. In [5, 5, 2], the first 5 ends up after the second one. If you need stability, use merge sort, or sort pairs of (value, original index) so that no two keys are equal.

Is heap sort an in-place sorting algorithm?

Yes. The heap is stored in the array itself: the parent of index i is (i − 1) // 2 and its children are 2i + 1 and 2i + 2, so no tree nodes or pointers are needed. With an iterative sift-down, as in the code on this page, the extra memory is a few index variables: O(1).

Why does heap sort use a max-heap for ascending order?

Because the largest value has to go to the end of the array first. A max-heap keeps the largest value at the root, so each round swaps it into the last free slot and the sorted part grows from the right. A min-heap would put the smallest value at the end and sort the array in descending order.

Is heap sort faster than quick sort?

Usually not in practice, even though its worst case is better. Heap sort makes more comparisons on average and jumps around memory, which is slow on large arrays. That is why libraries such as GCC's std::sort use quick sort first and switch to heap sort only when the recursion gets too deep.

Crio Software Development

Go from watching algorithms to using them

Crio's Software Development Fellowship has you practise data structures and algorithms by building real projects, the way they come up at work and in interviews. Start with a free trial session.

Explore the program

Free trial · No credit card required

Sources

  1. J. W. J. Williams, "Algorithm 232: Heapsort", Communications of the ACM 7(6), June 1964
    The original heapsort and the array layout of the heap.
  2. Robert W. Floyd, "Algorithm 245: Treesort 3", Communications of the ACM 7(12), December 1964
    Bottom-up heap construction: sift down from the last parent, the O(n) build used here.
  3. Sedgewick and Wayne, Algorithms (4th ed., Addison-Wesley, 2011)
    Section 2.4, Priority queues: sink-based heap construction uses fewer than 2N compares (Proposition Q); heapsort uses fewer than 2N lg N + 2N compares (Proposition R).
  4. Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms (3rd ed., MIT Press, 2009)
    Chapter 6, Heapsort: MAX-HEAPIFY, BUILD-MAX-HEAP in O(n) (Section 6.3) and HEAPSORT.
  5. Linux kernel, lib/sort.c
    The kernel's generic sort() is a heapsort; the comments explain why it is preferred over quicksort there.
  6. GCC libstdc++, bits/stl_algo.h
    std::sort is an introsort: the depth limit is 2·lg n, and at zero it heap-sorts the range (__partial_sort).

The animation, the worked example and the step counts are all generated by one implementation of heap sort, which is unit-tested against an independent version on edge cases and hundreds of random inputs. The Python, Java and JavaScript code is the exact code shown above, run on the same cases.

Last updated:

More algorithms, visualized

Every page runs real, tested code and lets you step through it with your own input.

All algorithms