Visual Algorithms • Sorting

Heap Sort

Build a Max-Heap, then Extract the Max

Heap Sort is a comparison sort that uses a binary heap structure. The core idea is simple: heapify the array into a max-heap, then repeatedly swap the root (largest) with the last element and heapify the reduced heap.

This page is designed as a teaching artifact: clear sections, progressive disclosure, and “what to watch for” cues so learners can connect the animation to the algorithm logic.

Demo / Media Pseudocode UXUI-Pedagogy-HCI

Overview

Heap Sort guarantees O(n log n) time and performs sorting in-place (constant extra memory). It’s a strong teaching algorithm because it shows how a data structure (heap) can power a sorting method.

This page teaches Heap Sort using a structured learning flow: Build Max-Heap → Repeated Extract-Max → Restore Heap. The UX goal is to make the algorithm feel “trackable” by showing learners: (1) where they are, (2) what changed, and (3) why the step matters.

The learning problem

Common breakdown

Beginners mix up heapify with sorting, don’t see why swapping happens, and get confused when the “sorted region” grows.

Key questions learners ask

“Why did that swap happen?”, “What is the heap now?”, “What part is already sorted?”, “What is the next step?”

Users & context

Primary: beginners in data structures / algorithms who learn best with visuals.
Secondary: instructors/TAs who need a clean artifact for demos and critique.
Environment: classroom projection, self-study, or short lab sessions.

Goals & success criteria

Learning goals

Explain the two phases: build heap and sort/extract.
Predict what happens next (swap vs sift-down).
Track the boundary between heap region and sorted region.

Success signals

Fewer “what just happened?” moments during demo.
Students can label the phase correctly.
Students can answer a 2–3 question checkpoint after the demo.

Demo / Media

Heap Sort Animation

This animation uses repeated Swap actions to visualize heapify operations and extraction. In the animation, the array starts as [4, 3, 1, 5, 2], each value is drawn inside a square, and swaps happen during heapify and extraction. :contentReference[oaicite:1]{index=1}

How the animation maps to the code

Array as “cards”

Squares are created for each element and centered with consistent spacing before sorting begins. :contentReference[oaicite:2]{index=2}

Swap = key learning moment

When the heap property is violated, the script swaps the two visual boxes using Manim’s Swap() and also swaps the array values to keep logic and visuals aligned. :contentReference[oaicite:3]{index=3}

heapify() is the “repair step”

The function compares root vs. left/right children and recursively heapifies the affected subtree after a swap. :contentReference[oaicite:4]{index=4}

Extraction = sorting progress

The loop swaps the root with the last element, shrinking the heap boundary each time, then heapifies again from the top. :contentReference[oaicite:5]{index=5}

Pseudocode

Read this while watching the animation: the “big idea” is build heap → extract max repeatedly.

HEAP-SORT(A):
		n = length(A)

		// 1) Build a max-heap
		for i = floor(n/2) - 1 down to 0:
			HEAPIFY(A, n, i)

		// 2) Extract max one-by-one
		for end = n - 1 down to 1:
			swap A[0], A[end]        // move max to its final place
			HEAPIFY(A, end, 0)       // restore heap in the remaining prefix

	HEAPIFY(A, heapSize, i):
	largest = i
	left  = 2*i + 1
	right = 2*i + 2

	if left  < heapSize and A[left]  > A[largest]: largest = left
	if right < heapSize and A[right] > A[largest]: largest = right

	if largest != i:
		swap A[i], A[largest]
		HEAPIFY(A, heapSize, largest)

Complexity

Time

Best / Avg / Worst: O(n log n)

Space

O(1) extra (in-place)

Stability

Not stable (swaps can reorder equals)

Teaching flow (scaffolded)

1) Build Max-Heap

Start with a clear goal: “Make the largest element easy to extract.” Show what heapify changes (local swaps) without jumping to the sorting phase.

2) Extract-Max (Swap)

Swap root with the last element in the heap region. Visually separate “sorted region” so learners see progress immediately.

3) Restore Heap (Sift-Down)

The swap breaks heap order—sift-down fixes it. This is where many learners get lost, so the UI should highlight the active path.

UX/UI • Pedagogy • HCI

This page intentionally uses structure and visual cues to reduce cognitive load for beginners.

UX/UI Design choices

Phase clarity: labels + section headers separate “Build Heap” from “Sorting.”
Progress visibility: a clear boundary for heap region vs sorted region.
Change emphasis: highlight only the elements that moved (swap + sift path).
Consistent layout: same card structure across pages reduces reading friction.

Pedagogy (teaching strategy)

Scaffolding: teach heap property first; only then teach extraction loop.
Chunking: one “meaningful unit” per step: swap → sift-down → done.
Checkpoints: small questions to confirm understanding before moving on.

HCI principles applied

Mental models: “root is max” + “sorted region grows” becomes predictable.
Recognition over recall: labels and boundaries reduce memory load.
Feedback: each step shows an immediate effect (progress + restored heap).
Cognitive load control: avoid showing too many highlights at once.

Evaluation plan (lightweight but real)

Method

Quick 10–15 minute usability/learning check with 3–5 learners: observe where they hesitate, what they mislabel, and what they predict incorrectly.

Tasks

Identify phase: “Are we heapifying or sorting right now?”
Predict next action: swap vs sift-down.
Mark boundary: which part is sorted?

Metrics

Time-to-correct explanation, number of confusion points, and a 1–5 confidence rating after the demo. (This is enough evidence for a micro case study.)

Iteration note: After the first test, I would refine labels, reduce highlight noise, and add a short “phase legend” if learners still confuse heapify vs sorting.