Computer Science · Grade 12

Active learning ideas

Heaps and Priority Queues

Active learning turns the abstract structure of heaps into a concrete experience. Students need to physically move elements, trace paths, and test operations to truly grasp why the heap property matters and how it behaves during insertions and deletions. These activities make the invisible mechanics of bubbling and heapifying visible through hands-on work.

• Ontario Curriculum Expectations
• CS.DSAA.10
• CS.P.10

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

Activity 01

• Simulation Game
• 35 min · Pairs

Card Simulation: Heap Insertions and Deletions

Provide students with numbered cards representing priorities. In pairs, they build a min-heap array on paper by inserting cards one by one and bubbling up. Then delete the root three times, heapifying down each time, and note the steps in a shared log.

Explain how a heap maintains its order property during insertion and deletion.

Facilitation Tip

During Card Simulation, have pairs trade their heap diagrams after each step so they check each other's bubbling or heapifying before moving on.

What to look for

Present students with a small array representing a min-heap. Ask them to identify the parent and child nodes for a given element and explain why the heap property holds or is violated. Then, ask them to predict the state of the heap after inserting a new value.

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

Activity 02

• Simulation Game
• 45 min · Pairs

Coding Pairs: Priority Queue Implementation

Pairs code a min-heap class with insert and extract-min methods using Python lists. Test with 10 sample priorities, timing operations. Compare results to a sorted list queue and discuss differences.

Compare the efficiency of a heap-based priority queue versus a sorted array-based priority queue.

Facilitation Tip

For Coding Pairs, require students to annotate their code with comments that map each line to a step in the heap algorithm, then pair-share to compare annotations.

What to look for

Pose the question: 'Imagine you are designing a system for emergency services dispatch. Would you use a min-heap or a max-heap for prioritizing calls, and why? Describe the key operations you would need and how the heap structure supports them.'

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

Activity 03

• Simulation Game
• 40 min · Small Groups

Benchmark Stations: Efficiency Comparison

Set up stations with pre-written code for heap and array priority queues. Small groups run timed tests on datasets of 100, 1000, and 10000 elements, graphing insert/extract times to visualize O(log n) versus O(n).

Design a system that uses a min-heap to manage tasks by their priority.

Facilitation Tip

At Benchmark Stations, assign one student in each group to record timing results while another writes the exact sequence of operations used so both roles contribute to the analysis.

What to look for

Provide students with a list of 5 tasks, each with a priority level (e.g., 1=highest, 5=lowest). Ask them to: 1. Draw the min-heap structure that would store these tasks. 2. Write the code snippet or pseudocode for extracting the highest priority task.

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

Activity 04

• Simulation Game
• 50 min · Small Groups

Design Challenge: Task Scheduler

Small groups design a priority queue system for job scheduling using a min-heap. Sketch the class, pseudocode operations, and simulate a scenario with 8 tasks. Present one use case to the class.

Explain how a heap maintains its order property during insertion and deletion.

What to look for

Present students with a small array representing a min-heap. Ask them to identify the parent and child nodes for a given element and explain why the heap property holds or is violated. Then, ask them to predict the state of the heap after inserting a new value.

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

A few notes on teaching this unit

Start with physical models before code. Research shows that students grasp tree operations better when they handle cards or tokens than when they first see code. Avoid rushing to abstraction—let them experience the swap chains and level shifts that define heap behavior. Use collaborative tracing to surface misconceptions early, and circulate to listen for language that reveals confusion about parent-child relationships.

By the end of these activities, students should confidently explain the heap property, trace insertion and deletion steps, and justify why the asymptotic costs make sense. They should also implement a priority queue and compare its performance to alternatives with clear reasoning.

---

Watch Out for These Misconceptions

• During Card Simulation: Heap Insertions and Deletions, watch for students who assume the entire level of the tree must be sorted because they see the root as the smallest element.

  Ask them to trace the specific path of a newly inserted element as it bubbles up, marking each swap and comparing the parent-child values step by step. Emphasize that only the path from the new leaf to the root must satisfy the heap property, not the entire level.

• During Coding Pairs: Priority Queue Implementation, watch for students who think swapping elements in the array is enough to maintain the heap property without verifying the child comparisons.

  Require them to write a helper function that checks the heap property along the path of each insertion and deletion, then run it after every operation to catch violations early.

• During Design Challenge: Task Scheduler, watch for students who argue that duplicates in priorities will break the extraction order.

  Give them a sample input with duplicate priorities and have them simulate the extraction process, comparing the order produced by their heap to the expected behavior. Ask them to explain why duplicates do not violate the heap property.

---

Methods used in this brief

• Simulation Game