Skip to content
Tutorials Center
My learning

Topics

Lesson 83 of 225 ยท Sorting

Heap Sort

Learn heap sort in Python: how a max-heap stored in a list sorts in place in O(n log n), with sift-down traces, build-heap analysis and a quick sort comparison.

Heap sort is the sorting algorithm that makes two promises at once: it always runs in O(n log n) time, even on the worst possible input, and it needs only O(1) extra memory because it sorts the list in place. Quick sort can be O(nยฒ) in bad cases, and merge sort needs a helper array. Heap sort has neither problem. In exchange it is usually slower in practice and it is not stable.

The algorithm uses a binary heap, a tree with one rule: every parent is at least as large as its children (a max-heap). The largest element is therefore always at the top. Heap sort turns the input into a max-heap, then repeatedly takes the top element, which is the largest remaining value, and puts it at the end of the list. This lesson builds it from scratch, traces it on a small list, proves where O(n log n) comes from, and compares it with the other sorts. If heaps are new to you, read Binary Heaps first; a short recap is included below.

Recap: a heap lives inside a list

A binary heap is a complete binary tree (every level full except possibly the last, which fills from the left). Because there are no gaps, the tree fits in a plain list without any node objects. For the element at index i (starting at 0):

  • left child: 2*i + 1
  • right child: 2*i + 2
  • parent: (i - 1) // 2
TEXT
list:   [90, 70, 80, 30, 60, 10, 50]

tree:            90 (0)
               /        \
          70 (1)        80 (2)
          /    \        /    \
      30 (3)  60 (4) 10 (5)  50 (6)

every parent >= both children  ->  valid max-heap

The key operation is sift down (also called heapify): if a node is smaller than one of its children, swap it with the larger child, and repeat from the child's position until the node is no longer smaller than its children or it has no children.

Python Sift down with a trace

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The root 10 is compared with its children 70 and 80 and swaps with the larger one (80). Then it is compared with its new children 20 and 50, swaps with 50, and ends as a leaf. The result is a valid max-heap. Each swap moves one level down, so a sift-down costs at most the height of the tree, which is about logโ‚‚ n.

Phase 1: build the max-heap

Given an arbitrary list, how do we make it a heap? One simple idea is to insert elements one at a time (as in heapq), which costs O(n log n). A smarter way works bottom-up: leaves are already valid one-element heaps, so start at the last node that has a child, n // 2 - 1, and sift down each node going backwards to the root. By the time you reach a node, both its subtrees are heaps, which is exactly the precondition sift-down needs.

Python Build a max-heap bottom-up

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You might expect n/2 sift-downs of up to log n steps each to cost O(n log n), and as an upper bound that is true. A sharper count shows the true cost is O(n). Most nodes are near the bottom, where the sift-down is short: about n/2 nodes are leaves (0 steps), n/4 nodes can move at most 1 step, n/8 at most 2, and so on. The total is n ร— (0/2 + 1/4 + 2/8 + 3/16 + ...) which adds up to at most n.

Phase 2: repeatedly take the maximum

Now the largest value sits at index 0. Swap it with the last element of the heap region: the maximum lands in its final sorted position, and the heap shrinks by one. The new root is probably out of place, so sift it down within the smaller heap. Repeat until the heap has one element.

TEXT
 heap region (shrinks)            | sorted region (grows)
 [ 9  7  8  3  5 ]                | 
 swap root with last  ->          
 [ 5  7  8  3 ]                   | 9
 sift down 5          ->
 [ 8  7  5  3 ]                   | 9
 swap root with last, shrink...
 [ 3  7  5 ]                      | 8 9
 ...

The array is split into two parts that move toward each other: a heap at the front, and a sorted tail at the back. No extra memory is needed.

Python Heap sort with a step-by-step trace

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The loop for end in range(n - 1, 0, -1) stops before index 0, because when only one element is left it is automatically the smallest and already in place.

Complexity

Part Cost Why
Build heap O(n) most nodes are near the leaves and sink only a step or two
n - 1 extractions O(n log n) each does one swap and a sift-down of at most about logโ‚‚ n levels
Total time O(n log n) in the best, average and worst case
Extra space O(1) everything happens inside the input list (iterative sift-down)

Heap sort is not adaptive: it does about the same work on sorted, reversed and shuffled data. Sorted input does not help, and it does not hurt, which is exactly why it has no bad case. Let us count the work to see this.

Python Counting comparisons on different inputs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The build phase stays under 2n comparisons for every input (the O(n) bound), and the total is in the same ballpark for all four inputs. The "all equal" case is cheaper because sift-down stops immediately when nothing is larger.

Not stable, and cache-unfriendly

Heap sort is not stable. The swap between the root and the last element, and the way sift-down jumps across the tree, can reorder equal keys. Here is a concrete case, sorting by the number only:

Python Heap sort is not stable

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

sorted keeps a, b, d in their original order within priority 2. Heap sort scrambles them. If you need to sort by several keys one after another, use a stable sort (Sorting Basics).

Heap sort is also slower than quick sort in practice. Quick sort scans neighboring memory cells, which suits CPU caches, while sift-down jumps between index i and 2i + 1, which are far apart for large lists. Both are O(n log n) in theory, but the constants differ.

Heap sort with Python's heapq

Python's standard library already provides a (min-)heap in heapq. A "heap sort" using it is two lines: push everything, pop in order. This version is not in place (it builds a second list), but it is the practical way to use a heap in Python and the heart of top-k and merging problems; see Heaps in Python: heapq.

Python Heap sort using heapq

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Heap sort versus the other sorts

Algorithm Worst time Extra space Stable Notes
Heap sort O(n log n) O(1) No guaranteed bound, in place
Quick sort O(nยฒ) O(log n) No fastest in practice with a good pivot
Merge sort O(n log n) O(n) Yes great for linked lists and external data
Insertion sort O(nยฒ) O(1) Yes tiny or nearly sorted inputs

Real libraries combine them: introsort starts with quick sort and switches to heap sort when the recursion gets too deep, so the worst case is capped at O(n log n); see Shell Sort, Timsort and Hybrid Sorts. Heap sort also shines when you need only the largest few items: build the heap once and take k elements in O(n + k log n), which is the idea behind Top-K problems.

Common mistakes

  • Using a min-heap for an ascending in-place sort. With a max-heap, the maximum goes to the end, so the list ends in ascending order. A min-heap would give a descending list.
  • Forgetting to shrink the heap. After swapping the root to the end, sift down only within a[:end]. Passing the full length undoes your sorted tail.
  • Wrong start of the build loop. Start at n // 2 - 1 (the last parent), not n - 1 or n // 2; leaves have nothing to sift.
  • Comparing against only one child. Sift-down must pick the larger of the two children, otherwise the heap property breaks on the other side.
  • Assuming stability. Equal keys can swap order.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which complexity does heap sort have in the worst case?

    Building the heap is O(n) and each of the n-1 extractions costs O(log n), so the total is O(n log n) no matter how the input is arranged.
  2. 2. Why does the bottom-up build-heap phase take only O(n) time?

    About half of the nodes are leaves that need no work, a quarter can move at most one level, and so on. The sum of all those short moves is linear.
  3. 3. Where does heap sort put the maximum after swapping the root with the last heap element?

    The maximum is moved to its final position at the end, the heap region shrinks by one, and the swapped-in value is sifted down.
  4. 4. What is the extra space of the in-place, iterative version of heap sort?

    Both the heap and the sorted tail live inside the input list, and an iterative sift-down needs only a few variables.
  5. 5. For the element at index i in a 0-based heap array, where is its left child?

    The left child is at 2i + 1 and the right child at 2i + 2. The expression (i - 1) // 2 gives the parent.

Summary

  • Heap sort builds a max-heap inside the list, then repeatedly swaps the root with the last heap element and sifts down in the shrunken heap.
  • Bottom-up heap construction starts at index n // 2 - 1 and costs O(n); the extraction phase costs O(n log n).
  • Worst, average and best cases are all O(n log n); extra space is O(1).
  • It is not stable and has poor cache behavior, so quick sort is faster in practice, but heap sort guarantees its bound.
  • Introsort uses heap sort as a safety net against quick sort's worst case.
  • In everyday Python, use heapq for priority queues and top-k tasks, and sorted for sorting.

Next: Counting, Radix and Bucket Sort, sorting without comparing elements at all.