Case Study • Advanced Algorithms

Heap Sort

A structured learning module for heap reasoning, heapify repair, and extraction-based sorting.

Heap Sort is harder than beginner sorting algorithms because learners must understand the heap structure before the sorting loop makes sense. They are not just sorting values — they are maintaining a max-heap, repairing violations, and shrinking the heap boundary over time.

This module focuses on the mental model learners need most: first build and maintain the max-heap, then repeatedly move the maximum value to the sorted region while restoring the heap property.

Watch Demo Guided Worksheet

Project Scope

Curricular Target

Data Structures, Algorithms, and intermediate sorting lessons that connect trees to array-based procedures.

Delivery Model

Hybrid instructional module; adaptable for lecture, guided tracing, or asynchronous review.

Learner Profile

Students moving from simple comparison sorts to algorithms that depend on an underlying data structure.

Primary Objective

Enable learners to explain how Heap Sort builds a max-heap, extracts the maximum repeatedly, and restores the heap after each swap.

Core Learning Outcomes

Explain the max-heap property and how it supports sorting.
Distinguish between the heap-building phase and the extraction phase.
Trace heapify operations step by step.
Predict how the heap boundary changes as sorted values accumulate on the right.

Learning Challenge

Heap Sort is difficult because learners must track two systems at once: the internal heap structure and the growing sorted region. A common confusion is not knowing whether the current step is repairing the heap or moving the maximum value into its final place.

Design Strategy

Heap Before Sort

The lesson introduces the heap property first so learners can understand the structure before the sorting loop begins.

Heapify as Repair

Heapify is shown as a repair process, helping learners see why swaps happen and what invariant is being restored.

Boundary Between Heap and Sorted Region

The lesson makes the heap region and sorted region visually distinct so learners can tell which part of the array is still active.

Repeated Pattern Recognition

Every extraction follows the same pattern: swap max to the end, shrink the heap, then heapify again.

Core Conceptual Model

Heap Sort works in two major phases. First, the array is transformed into a max-heap, where each parent is greater than or equal to its children. Then the root (maximum value) is swapped to the end, the heap shrinks, and the remaining unsorted portion is repaired through heapify.

Algorithm Process

Build a max-heap from the unsorted array.
Swap the root with the last value in the heap.
Shrink the heap boundary by one.
Heapify the root to restore the max-heap property.
Repeat until the heap region is empty and the full array is sorted.

Performance & Properties

Time: O(n log n)
Space: O(1), in-place
Stability: Not stable
Learning Value: Strong for connecting tree structure, array representation, and sorting logic.

Common Learner Misconceptions

Confusing heap construction with the sorting loop.
Not recognizing that heapify is repairing a violation, not performing general sorting.
Forgetting that the sorted region grows from the right side of the array.
Assuming the heap property still applies to values that have already moved into the sorted region.

Solution Design

The learning sequence is structured to separate structural understanding from sorting behavior so learners can master one layer at a time.

1. Heap Property Before Sorting

The lesson begins by helping learners understand what a max-heap is and why the largest value appears at the root.

2. Heapify as Local Repair

Heapify is treated as a focused repair step. Learners track which child is larger, why a swap happens, and how the violation moves downward.

3. Extraction as Boundary Shift

When the root swaps with the last heap element, the lesson marks that value as sorted and shrinks the active heap region.

4. Two-Phase Repetition

Each cycle repeats the same logic: extract the max, then repair the heap. This repetition helps learners separate the two actions instead of blending them together.

5. Structure and Sort Connected at the End

The lesson closes by showing that the sorted array is the result of repeatedly using the heap’s structural advantage, not a separate sorting trick.

Design Refinement:

Early confusion often centered on whether the learner should focus on the heap shape or the sorted region during extraction.

To address this, the heap and sorted boundary were visually separated, and the lesson emphasized whether each step was an extraction move or a heapify repair.

Interactive Implementation

The animation isolates heapify actions before and after extraction so learners can follow the structural logic behind each swap.

Watch actively: pause, predict whether the next step is a max extraction or a heap repair, and decide which value should move next.

The implementation emphasizes the repeated cycle of root extraction, boundary shrink, and heapify repair so learners can see how Heap Sort combines a data structure with a sorting process.

Guided Worksheet (Pause & Predict)

These worksheet prompts are designed to support active learning during the animation. Pause the video at each major step, predict what will happen next, then continue to confirm or revise your reasoning.

Part 1 — Reading the Current Heap

Does the current structure satisfy the max-heap property?
Which value is at the root right now?
Why is the root the next candidate for extraction?

Part 2 — Predict the Extraction

Which value will move to the sorted region next?
Where will the heap boundary move after the swap?
Why is the heap not fully valid immediately after extraction?

Part 3 — Predict the Heapify Repair

Which child should be compared first during heapify?
Should the current node swap with one of its children, and why?
How will the heap look after the repair is complete?

Focus on the repeated cycle: extract the maximum, shrink the heap, then repair the structure with heapify.

Assessment Strategy

This module evaluates understanding through guided prediction, heapify tracing, and interpretation of the changing heap boundary.

Formative assessment (during learning): Students predict whether the next step is extraction or repair and explain why a swap should happen.
- Are we extracting the maximum or restoring the heap?
- Which value should move next, and why?
- What invariant must be restored after this step?
Application assessment (state + process): Students explain how each cycle changes the heap and the sorted region.
- Which value is now in the sorted region?
- How has the heap boundary changed?
- What part of the structure still requires heapify?
Summative assessment (after learning): A short exit check confirms whether students can explain both the role of the heap and the sorting loop.
- Why does Heap Sort begin with a max-heap?
- What is the purpose of heapify after each extraction?
- How does Heap Sort guarantee O(n log n) time?

Assessment Activities

Prediction prompts before each extraction and heapify step.
Heap-boundary checks showing how the sorted region grows over time.
Repair-tracing questions during sift-down.
Comparison questions contrasting Heap Sort with simpler comparison-based sorts.

Inclusive Design

Explicit heap and sorted-region cues reduce cognitive search during extraction.
Separation of extraction and repair supports learners who need a slower reasoning tempo.
Pacing control supports repeated review of each cycle.
Guided worksheet prompts support different learning preferences.

Instructional Impact

The module helps learners move from seeing Heap Sort as a confusing combination of trees and sorting into understanding it as a structured cycle of max extraction, shrinking boundary, and heap repair.