AAlgorithm LabLesson 06

Sorting · Intermediate

Build a max heap.
Extract the maximum.

Heap Sort turns an array into a complete binary tree, keeps the largest remaining value at the root, and moves that root into the final sorted suffix.

Start visualizing How it works
Mini example[ 4, 10, 3 ]
01
4103
array tree
02
1043
max heap
03
3410
extract

Key idea The tree is only a way to read the array: children of index i live at 2i + 1 and 2i + 2.

Before you start

What you will learn

A clear finish line for the lesson, plus the small amount of knowledge you need before beginning.

Learning objectives
  1. Translate between an array index and its parent or child positions.
  2. Explain why bottom-up heap construction starts at the last parent.
  3. Trace a root extraction and the sift-down repair that follows it.
  4. Compare Heap Sort's guaranteed runtime and memory use with Merge Sort and Quick Sort.
01Understand02Visualize03Trace04Code05Complexity06Quiz07Challenge08Use cases

01 — The idea

Think tree, store array

How can one array behave like a priority structure without allocating tree nodes?

1
i2i+12i+2

Read parent and children

Treat index 0 as the root. For index i, its children are at 2i + 1 and 2i + 2 when those indexes exist.

2
10≥79

Build a max heap

Starting at the last parent, sift values downward until every parent is at least as large as both children.

3
3410

Extract and repair

Swap the root maximum with the heap's final item, shrink the heap, then sift the new root down again.

02 — Try it yourself

Watch the heap grow, shrink, and repair

See the same values as a tree and an array while the active heap shrinks and the sorted suffix grows.

3–10 values, each from 1 to 99
Phase BuildHeap size 7 Paused
Same data in array storagesorted suffix is outside the heap
Active heap: indexes 0–6Sorted: 0Root: —
↧

Read the array as a complete binary tree. Build the max heap from the last parent upward.

Comparisons0
Swaps0
Extractions0
Parent Larger child Sorted
Dry-run trace

Turn each animation into a written decision

The latest eight Heap Sort decisions
StepPassActionParent / childrenHeap arraySwaps
0BuildReady—[4, 10, 3, 5, 1, 8, 2]0

The highlighted row always matches the visualization above. Step forward to extend the trace.

03 — Read the code

From child indexes to working code

Compare the same bottom-up build, root extraction, and iterative sift-down across all four languages.

heap-sort.mjs
01export function heapSort(numbers) {02  const array = [...numbers];03 04  for (let root = Math.floor(array.length / 2) - 1; root >= 0; root -= 1) {05    siftDown(array, root, array.length);06  }07 08  for (let end = array.length - 1; end > 0; end -= 1) {09    [array[0], array[end]] = [array[end], array[0]];10    siftDown(array, 0, end);11  }12  return array;13}14 15function siftDown(array, root, size) {16  while (2 * root + 1 < size) {17    const left = 2 * root + 1;18    const right = left + 1;19    let largest = left;20    if (right < size && array[right] > array[left]) largest = right;21    if (array[root] >= array[largest]) return;22    [array[root], array[largest]] = [array[largest], array[root]];23    root = largest;24  }25}

04 — Avoid the traps

Common mistakes

These bugs often produce an answer that looks almost right. Learn the symptom and the correction together.

01

Mixing heap size with array length

Symptom: A value already placed in the sorted suffix gets pulled back into the heap.

Correction: Pass the shrinking heap size into sift-down and ignore every index at or beyond it.

02

Swapping with the left child automatically

Symptom: The parent can remain smaller than its right child, so the max-heap rule is still broken.

Correction: Compare both children first, then swap with the larger valid child.

03

Starting heap construction at the last element

Symptom: Extra calls inspect leaves that already satisfy the heap rule.

Correction: Start at floor(n / 2) - 1, the final index that can have a child.

05 — Check yourself

Check your understanding

Answer 4 questions, then reveal the reasoning. Your progress stays on this device—no account required.

0 of 4 answered
Q1Where are the children of array index i in a zero-based heap?
Q2After swapping the root with the heap's final value, what happens next?
Q3What is Heap Sort's worst-case runtime?
Q4Why is standard in-place Heap Sort unstable?

Answer every question to check your work.

06 — Mini game

Repair the max heap

A small value is sitting at the root. Choose the correct child at each level to sift it into place.

Rule Swap with the larger child whenever that child is greater than the current parent.
Repair index 00 picks
4index 0
10index 1
7index 2
2index 3
5index 4
3index 5
Which child should swap with 4?
↧

Compare both children and choose the larger one.

07 — Use it wisely

Where Heap Sort fits

⌁

Predictable sorting

Heap Sort keeps O(n log n) time even when the input order is adversarial.

Guaranteed bound
□

Tight memory

The array representation and iterative sift-down use constant auxiliary space.

Excellent fit
⇅

Priority structures

The same heap mechanics power priority queues and top-k selection workflows.

Transferable skill
×

Stable record sorting

Long-distance swaps do not preserve the original order of equal records.

Choose a stable sort

Lesson progress

Finish this lesson with confidence

Use this private checklist to confirm what you learned. Progress stays only in this browser.

0 of 4 complete0%

Complete every checklist item to finish the lesson.