Project 9: Heap and Priority Queue

Build a binary heap and use it to power priority queue operations.

Quick Reference

Attribute Value
Difficulty Level 2: Intermediate
Time Estimate 1-2 weeks
Language C (Alternatives: Python, Java, Go)
Prerequisites Projects 2 and 8, array manipulation
Key Topics Heaps, priority queues, heap sort

1. Learning Objectives

By completing this project, you will:

  1. Implement a binary heap in an array.
  2. Support push, pop, peek, and heapify operations.
  3. Use the heap for a priority queue and heap sort.
  4. Analyze time complexity and memory usage.

2. Theoretical Foundation

2.1 Core Concepts

  • Heap property: Parent is always >= (max-heap) or <= (min-heap) children.
  • Array representation: Children of index i are 2i+1 and 2i+2.
  • Heapify: Restore heap property after inserts/removals.
  • Priority queue: A heap-backed structure with O(log n) insert/remove.

2.2 Why This Matters

Heaps are essential for scheduling, shortest path algorithms, and efficient selection of min/max elements.

2.3 Historical Context / Background

Heaps and heap sort were introduced by Williams in the 1960s as a memory-efficient sorting technique.

2.4 Common Misconceptions

  • Misconception: Heaps are sorted trees. Reality: Only the root is guaranteed min/max.
  • Misconception: Heap sort is always faster than quicksort. Reality: It has worse cache behavior.

3. Project Specification

3.1 What You Will Build

A heap library with operations for insert, extract, build-heap, and heap sort, plus a priority queue demo.

3.2 Functional Requirements

  1. Heap operations: insert, peek, extract.
  2. Heapify: build heap from array in O(n).
  3. Heap sort: sort an array using heap.
  4. Priority queue demo: task scheduling by priority.

3.3 Non-Functional Requirements

  • Performance: O(log n) per insert/extract.
  • Reliability: Correct handling of empty heap.
  • Usability: Clear API for min-heap and max-heap.

3.4 Example Usage / Output

$ ./heap-demo
> push 5
> push 2
> push 8
> pop
8
> pop
5

3.5 Real World Outcome

You will be able to enqueue tasks with priorities and always extract the highest priority task first. Heap sort will output a fully sorted array.

4. Solution Architecture

4.1 High-Level Design

┌───────────┐     ┌──────────────┐     ┌─────────────┐
│ CLI/Test  │────▶│ Heap Library │────▶│ PQ Demo     │
└───────────┘     └──────────────┘     └─────────────┘

4.2 Key Components

Component Responsibility Key Decisions
heap.c Core heap ops Min-heap vs max-heap flag
pq.c Priority queue wrapper Struct with value + priority
demo.c CLI demo Simple commands

4.3 Data Structures

typedef struct {
    int* data;
    size_t size;
    size_t capacity;
} Heap;

4.4 Algorithm Overview

Key Algorithm: Sift Down

  1. Compare node with children.
  2. Swap with larger child (max-heap).
  3. Continue until heap property restored.

Complexity Analysis:

  • Time: O(log n)
  • Space: O(1)

5. Implementation Guide

5.1 Development Environment Setup

cc -Wall -Wextra -o heap-demo src/*.c

5.2 Project Structure

heap/
├── src/
│   ├── heap.c
│   ├── heap.h
│   ├── pq.c
│   ├── demo.c
├── tests/
└── README.md

5.3 The Core Question You’re Answering

“How can we always extract the highest priority item efficiently?”

5.4 Concepts You Must Understand First

Stop and research these before coding:

  1. Array-based tree indexing
  2. Heapify vs insert
  3. Priority queue use cases

5.5 Questions to Guide Your Design

  1. Will you support both min-heap and max-heap?
  2. How will you resize the array for growth?
  3. How will you represent priorities in the queue?

5.6 Thinking Exercise

Given array [3, 1, 6, 5, 2, 4], perform build-heap step by step.

5.7 The Interview Questions They’ll Ask

  1. Implement heapify in O(n).
  2. Explain why heap sort is O(n log n).
  3. What is the difference between heap and BST?

5.8 Hints in Layers

Hint 1: Start with max-heap It is easier to test by popping max values.

Hint 2: Build-heap from middle Start heapify from the last non-leaf.

Hint 3: Use helper functions Parent and child index helpers reduce bugs.

5.9 Books That Will Help

Topic Book Chapter
Heaps “Introduction to Algorithms” Ch. 6
Priority queues “Algorithms, Fourth Edition” Section 2.4

5.10 Implementation Phases

Phase 1: Foundation (3-4 days)

Goals:

  • Implement heap insert/extract
  • Add tests

Tasks:

  1. Implement sift up and sift down.
  2. Add simple unit tests.

Checkpoint: Heap property holds after operations.

Phase 2: Build-Heap and Sort (3-4 days)

Goals:

  • Implement build-heap
  • Implement heap sort

Tasks:

  1. Build heap in O(n).
  2. Use heap to sort arrays.

Checkpoint: Heap sort output is sorted.

Phase 3: Priority Queue Demo (2-3 days)

Goals:

  • Wrap heap in PQ interface
  • Add CLI demo

Tasks:

  1. Create struct with value + priority.
  2. Implement enqueue/dequeue.

Checkpoint: Highest priority task dequeued first.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Heap type min, max max (default) Clear testing
Resize policy double, fixed double Amortized O(1)
PQ structure separate arrays, struct struct Simpler mapping

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Tests Heap operations insert/extract
Integration Tests Heap sort random arrays
Edge Case Tests Empty heap pop on empty

6.2 Critical Test Cases

  1. Insert descending values then extract all.
  2. Build-heap from random array.
  3. Heap sort with duplicates.

6.3 Test Data

[5, 3, 8, 1, 2]
[1, 1, 1, 1]

7. Common Pitfalls and Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Wrong child index Out-of-bounds Check 2i+1, 2i+2
Not updating size Corrupt heap Update size on insert/extract
Confusing min/max Wrong ordering Use comparator function

7.2 Debugging Strategies

  • Print heap array after each operation.
  • Validate heap property with a checker.

7.3 Performance Traps

Rebuilding heap for each insert is O(n log n); use sift up instead.

8. Extensions and Challenges

8.1 Beginner Extensions

  • Add a heap property validator.
  • Add min-heap mode.

8.2 Intermediate Extensions

  • Support decrease-key operation.
  • Use heap in Dijkstra’s algorithm.

8.3 Advanced Extensions

  • Implement a d-ary heap.
  • Compare heap vs balanced BST performance.

9. Real-World Connections

9.1 Industry Applications

  • Task scheduling systems
  • Priority queues in pathfinding and networking
  • BinaryHeap in Rust stdlib
  • heapq in Python

9.3 Interview Relevance

Heaps are a common data structure in interview questions (top-k, streaming median).

10. Resources

10.1 Essential Reading

  • “Introduction to Algorithms” - Ch. 6
  • “Algorithms, Fourth Edition” - Section 2.4

10.2 Video Resources

  • Heap visualizations and heap sort animations

10.3 Tools and Documentation

  • Python heapq docs for reference

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain heap properties.
  • I can build a heap in O(n).
  • I can explain why heap sort is O(n log n).

11.2 Implementation

  • Heap operations pass tests.
  • Priority queue works as expected.

11.3 Growth

  • I can use heaps in other algorithms.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Heap with insert/extract
  • Basic tests

Full Completion:

  • Build-heap and heap sort
  • Priority queue demo

Excellence (Going Above and Beyond):

  • Decrease-key support
  • Dijkstra integration

This guide was generated from LEARN_ALGORITHMS_DEEP_DIVE.md. For the complete learning path, see the parent directory.