Computer Science · 12th Grade

Active learning ideas

Heap Sort and Priority Queues

Active learning works for Heap Sort and Priority Queues because the abstract properties of binary heaps become concrete when students physically arrange elements or trace operations by hand. The human-scale activities in this set build intuition for how the heap property is maintained and why the O(n log n) performance emerges from repeated heapify steps.

• Common Core State Standards
• CSTA: 3B-AP-10
• CSTA: 3B-AP-11
• CSTA: 3B-AP-12

• 25–35 min
• Pairs → Whole Class
• 4 activities

Activity 01

• Simulation Game
• 30 min · Whole Class

Simulation Game: Human Heap Construction

Write numbers on index cards and have students arrange themselves to form a valid max-heap, where each person must hold a number larger than both their children. Insert new students one at a time and ask the class to determine where they go and which swaps are needed to restore the heap property.

Explain how a heap maintains its properties during insertion and deletion operations.

Facilitation Tip

During Human Heap Construction, walk the room holding a deck of numbered cards and physically re-shape the heap whenever a swap is called for so every student sees the tree rebalance in real time.

What to look for

Present students with an array representing a max-heap. Ask them to identify the parent and child nodes for a given element and explain why the heap property holds. Then, ask them to demonstrate the first step of extracting the maximum element.

• Apply
• Analyze
• Evaluate
• Create
• Social Awareness
• Decision-Making

Activity 02

• Think-Pair-Share
• 25 min · Pairs

Think-Pair-Share: Priority Queue Design Challenge

Present 3 real-world systems: hospital emergency triage, CPU task scheduler, and print queue. Pairs decide the priority metric for each, what happens when two items have equal priority, and whether a max-heap or min-heap is more natural. Groups share and defend their design choices.

Compare the efficiency of Heap Sort with other O(N log N) sorting algorithms.

Facilitation Tip

For the Priority Queue Design Challenge, provide a simple scenario sheet and colored sticky notes so pairs can iteratively refine their min-heap or max-heap choice and priority tie-breaker rule in visible layers.

What to look for

Pose the question: 'Imagine you are designing a system to manage emergency room patient wait times. Would a priority queue be a suitable data structure? Justify your answer by explaining how you would assign priorities and which heap property (min or max) would be most appropriate.'

• Understand
• Apply
• Analyze
• Self-Awareness
• Relationship Skills

Activity 03

• Problem-Based Learning
• 35 min · Small Groups

Problem Solving: Heapify from Scratch

Give student groups an unsorted array of 10 integers. Groups build the heap manually step by step using the bottom-up heapify procedure, drawing each step as a tree diagram. Groups then perform the sort phase and compare final arrays to verify correctness.

Design a system where a priority queue would be the most appropriate data structure.

Facilitation Tip

When students Heapify from Scratch, give each group a mini-whiteboard and insist they annotate each step with the current index, parent, and child values to force precise index arithmetic.

What to look for

Provide students with a small unsorted array. Ask them to draw the initial max-heap structure after building it. Then, ask them to write the time complexity for building the heap and for extracting the maximum element once.

• Analyze
• Evaluate
• Create
• Decision-Making
• Self-Management
• Relationship Skills

Activity 04

• Gallery Walk
• 25 min · Pairs

Gallery Walk: Heap Operation Complexity Cards

Post cards for each heap operation (insert, extract-max, peek, heapify) with a complexity claim and brief justification. Students annotate whether they agree, challenge the justification, and draw a small example that supports or refutes the claim.

Explain how a heap maintains its properties during insertion and deletion operations.

Facilitation Tip

During the Gallery Walk, pre-print three large index cards for each heap operation (build, extract-max, heapify-down) and have students place them in the correct O(log n) or O(n) buckets before moving on.

What to look for

Present students with an array representing a max-heap. Ask them to identify the parent and child nodes for a given element and explain why the heap property holds. Then, ask them to demonstrate the first step of extracting the maximum element.

• Understand
• Apply
• Analyze
• Create
• Relationship Skills
• Social Awareness

A few notes on teaching this unit

Start with the Human Heap activity to ground the tree metaphor in physical space before any code appears. Avoid rushing to pseudocode; let students feel the repeated swaps and rotations that make the heap property hold. Use concrete timing examples—such as emergency room triage—to anchor the difference between priority order and arrival order early, because once students conflate these it is hard to undo.

By the end of these activities, students will be able to construct a max-heap from raw data, explain why the heap property is not full sorting, and choose the correct heap variant for a priority-queue scenario. They should also articulate the trade-offs between Heap Sort and other O(n log n) sorts in terms of cache behavior.

---

Watch Out for These Misconceptions

• During Human Heap Construction, students may assume the final heap is sorted left-to-right.

  Pause the human heap and ask each student to point to the largest element, then the second largest, to show that only the root is guaranteed maximal and the rest are partially ordered.

• During Priority Queue Design Challenge, students believe any heap can serve as a stable priority queue.

  Have pairs add an extra column to their sticky-note design sheet labelled 'tie-breaker' and require them to explain why a timestamp is needed to enforce FIFO within the same priority level.

• During Heapify from Scratch, students claim Heap Sort runs in O(n) because building the heap feels fast.

  Ask each group to time their build-heap step on a 1,000-element array and compare it to an O(n log n) line on a shared graph to make the linear build versus logarithmic extract trade-off visible.

---

Methods used in this brief

• Simulation Game
• Think-Pair-Share
• Problem-Based Learning
• Gallery Walk