Generic Priority Queue

Problem Statement

Build a generic priority queue data structure that can work with any type implementing Ord. The queue should support:

Inserting elements with automatic ordering
Removing the highest priority element
Peeking at the highest priority element without removing it
Custom comparison strategies through trait bounds
Efficient implementation using a binary heap
Support for both min-heap and max-heap configurations using phantom types

The priority queue must be fully generic over the element type and provide compile-time guarantees about ordering requirements.

Key Concepts Explained

1. Generic Type Parameters

Generic type parameters allow writing code that works with any type, determined at compile-time.

Without generics (code duplication):

#![allow(unused)]
fn main() {
struct IntQueue {
    items: Vec<i32>,  // Only works with i32
}

struct StringQueue {
    items: Vec<String>,  // Duplicate code for String!
}

struct TaskQueue {
    items: Vec<Task>,  // Duplicate code for Task!
}
// 3 nearly identical implementations!
}

With generics (single implementation):

#![allow(unused)]
fn main() {
struct PriorityQueue<T> {
    items: Vec<T>,  // Works with ANY type T
}

// One implementation serves all types:
let int_queue: PriorityQueue<i32> = PriorityQueue::new();
let string_queue: PriorityQueue<String> = PriorityQueue::new();
let task_queue: PriorityQueue<Task> = PriorityQueue::new();
}

How it works:

<T> declares a type parameter (placeholder for any type)
Compiler generates specialized code for each concrete type used
Called monomorphization: PriorityQueue<i32> and PriorityQueue<String> become separate compiled functions
Zero runtime cost: as fast as hand-written type-specific code

Multiple type parameters:

#![allow(unused)]
fn main() {
struct PriorityQueue<T, Order = MinHeap> {
    //                  ^       ^^^^^^^^^
    //                  |       Default value
    //                  Type parameter
    heap: Vec<T>,
    _order: PhantomData<Order>,
}

// Can specify Order or use default:
let min: PriorityQueue<i32> = PriorityQueue::new();  // Uses MinHeap
let max: PriorityQueue<i32, MaxHeap> = PriorityQueue::new();  // Uses MaxHeap
}

2. Trait Bounds (Constraining Generic Types)

Trait bounds specify what capabilities a generic type must have.

Problem without bounds:

#![allow(unused)]
fn main() {
struct PriorityQueue<T> {
    heap: Vec<T>,
}

impl<T> PriorityQueue<T> {
    fn push(&mut self, item: T) {
        self.heap.push(item);
        // How do we compare items to maintain heap order?
        // if self.heap[i] > self.heap[parent] { ... }  // ERROR: T might not support >
    }
}
}

Solution with trait bounds:

#![allow(unused)]
fn main() {
impl<T: Ord> PriorityQueue<T> {
    //   ^^^^^ Trait bound: T must implement Ord
    fn push(&mut self, item: T) {
        self.heap.push(item);
        if self.heap[i] > self.heap[parent] {  // OK! Ord provides >
            self.heap.swap(i, parent);
        }
    }
}
}

Common trait bounds:

#![allow(unused)]
fn main() {
T: Ord              // Can compare with <, >, ==
T: Clone            // Can clone values
T: Debug            // Can format with {:?}
T: Ord + Clone      // Multiple bounds
T: Ord + Clone + Send  // Even more bounds
}

Where clauses (cleaner syntax for complex bounds):

#![allow(unused)]
fn main() {
// Inline bounds (gets messy):
impl<T: Ord + Clone, Order: HeapOrder + Default> PriorityQueue<T, Order> { ... }

// Where clause (cleaner):
impl<T, Order> PriorityQueue<T, Order>
where
    T: Ord + Clone,
    Order: HeapOrder + Default,
{
    // Implementation
}
}

Why bounds matter:

Compile-time checking: Prevents using PriorityQueue<Vec<i32>> (Vec doesn’t implement Ord)
Clear API contracts: “This function needs types that can be compared”
Better error messages: Compiler tells you exactly what trait is missing

3. PhantomData and Zero-Sized Types (ZSTs)

PhantomData is a marker type that exists only at compile-time (zero bytes at runtime).

The problem:

#![allow(unused)]
fn main() {
struct PriorityQueue<T, Order> {
    heap: Vec<T>,
    // ERROR: Order is unused!
    // Compiler: "parameter `Order` is never used"
}
}

Rust requires all type parameters to be used in fields, but Order is only used for compile-time dispatch (not stored).

Solution with PhantomData:

#![allow(unused)]
fn main() {
use std::marker::PhantomData;

struct PriorityQueue<T, Order> {
    heap: Vec<T>,
    _order: PhantomData<Order>,  // Tells compiler: "Order is used (just not at runtime)"
}

impl<T: Ord, Order: HeapOrder> PriorityQueue<T, Order> {
    fn new() -> Self {
        PriorityQueue {
            heap: Vec::new(),
            _order: PhantomData,  // Zero bytes!
        }
    }
}
}

Memory proof (PhantomData is zero-sized):

#![allow(unused)]
fn main() {
use std::mem;

assert_eq!(mem::size_of::<PhantomData<MinHeap>>(), 0);
assert_eq!(
    mem::size_of::<PriorityQueue<i32, MinHeap>>(),
    mem::size_of::<Vec<i32>>()  // Same size as Vec alone!
);
}

When to use PhantomData:

Type parameter used for compile-time dispatch (not stored)
Type parameter affects variance/lifetime rules
Building state machines with phantom types

Real-world examples:

std::marker::PhantomData in smart pointers (Rc, Arc)
Typestate pattern (compile-time state machines)
Phantom types for units (meters vs feet)

4. Phantom Types for Compile-Time Dispatch

Phantom types use zero-sized marker types to change behavior at compile-time without runtime cost.

The problem: Want both min-heap and max-heap without code duplication.

Bad solution (code duplication):

#![allow(unused)]
fn main() {
struct MinHeap<T> {
    heap: Vec<T>,
}

impl<T: Ord> MinHeap<T> {
    fn sift_down(&mut self, i: usize) {
        if self.heap[i] > self.heap[child] { swap }  // Min-heap logic
    }
}

struct MaxHeap<T> {
    heap: Vec<T>,
}

impl<T: Ord> MaxHeap<T> {
    fn sift_down(&mut self, i: usize) {
        if self.heap[i] < self.heap[child] { swap }  // Max-heap logic (ONLY difference!)
    }
}
// 99% duplicate code!
}

Good solution (phantom types):

#![allow(unused)]
fn main() {
// Marker types (zero-sized)
struct MinHeap;
struct MaxHeap;

// Trait defines behavior difference
trait HeapOrder {
    fn should_swap<T: Ord>(parent: &T, child: &T) -> bool;
}

impl HeapOrder for MinHeap {
    fn should_swap<T: Ord>(parent: &T, child: &T) -> bool {
        parent > child  // Min-heap: parent should be smaller
    }
}

impl HeapOrder for MaxHeap {
    fn should_swap<T: Ord>(parent: &T, child: &T) -> bool {
        parent < child  // Max-heap: parent should be larger
    }
}

// Single implementation for both!
struct PriorityQueue<T, Order = MinHeap> {
    heap: Vec<T>,
    _order: PhantomData<Order>,  // Zero bytes!
}

impl<T: Ord, Order: HeapOrder> PriorityQueue<T, Order> {
    fn sift_down(&mut self, i: usize) {
        if Order::should_swap(&self.heap[i], &self.heap[child]) {
            // Compiler generates different code for MinHeap vs MaxHeap
            self.heap.swap(i, child);
        }
    }
}
}

Compile-time dispatch:

#![allow(unused)]
fn main() {
let min: PriorityQueue<i32, MinHeap> = PriorityQueue::new();
// Compiler generates: if parent > child { swap }

let max: PriorityQueue<i32, MaxHeap> = PriorityQueue::new();
// Compiler generates: if parent < child { swap }
}

Benefits:

Zero runtime cost: Compiles to same assembly as hand-written code
Type safety: Can’t mix min-heap and max-heap operations
DRY: Single implementation for all variants
No virtual dispatch: Unlike dyn Trait, phantom types resolve at compile-time

5. Ord and PartialOrd Traits (Comparison)

Ord and PartialOrd define how types are compared.

Hierarchy:

PartialEq  ─┬─> Eq ──────────> Ord
            │
            └──────────> PartialOrd ──┘

PartialOrd: Partial ordering (some values incomparable)

#![allow(unused)]
fn main() {
// f64 has PartialOrd (not Ord) because NaN is incomparable
let a = 1.0;
let b = 2.0;
let nan = f64::NAN;

assert!(a < b);         // true
assert!(!(nan < b));    // NaN is incomparable
assert!(!(nan == nan)); // NaN != NaN
}

Ord: Total ordering (all values comparable)

#![allow(unused)]
fn main() {
// i32 has Ord (all values comparable)
let a = 1;
let b = 2;

assert!(a < b);  // Always true or false, never incomparable
}

Implementing Ord:

#![allow(unused)]
fn main() {
#[derive(Debug, PartialEq, Eq)]
struct Task {
    priority: u8,
    name: String,
}

impl Ord for Task {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        // Compare by priority (higher first), then name
        other.priority.cmp(&self.priority)  // Reversed for max-heap
            .then(self.name.cmp(&other.name))
    }
}

impl PartialOrd for Task {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))  // Delegate to Ord
    }
}
}

Why PriorityQueue needs T: Ord:

Must be able to compare any two elements
PartialOrd isn’t enough (what if comparison returns None?)
Ord guarantees total ordering (always get Less, Equal, or Greater)

6. Newtype Pattern (Wrapper Types for Custom Ord)

Newtype pattern: Wrap a type to provide different behavior without changing the original.

Problem: Type has one Ord implementation, but you need different orderings.

#![allow(unused)]
fn main() {
struct Task {
    name: String,
    priority: u8,
    deadline: u64,
}

// Default Ord: compare by name
impl Ord for Task {
    fn cmp(&self, other: &Self) -> Ordering {
        self.name.cmp(&other.name)
    }
}

// But sometimes we want to compare by priority!
// Can't have two Ord implementations on Task.
}

Solution: Wrapper types:

#![allow(unused)]
fn main() {
// Wrapper changes comparison behavior
struct ByPriority(Task);  // Newtype wrapper

impl Ord for ByPriority {
    fn cmp(&self, other: &Self) -> Ordering {
        self.0.priority.cmp(&other.0.priority)  // Compare by priority!
    }
}

struct ByDeadline(Task);  // Another wrapper

impl Ord for ByDeadline {
    fn cmp(&self, other: &Self) -> Ordering {
        self.0.deadline.cmp(&other.0.deadline)  // Compare by deadline!
    }
}

// Now can use different orderings:
let by_priority: PriorityQueue<ByPriority> = PriorityQueue::new();
let by_deadline: PriorityQueue<ByDeadline> = PriorityQueue::new();
}

Generic wrapper (field extractor):

#![allow(unused)]
fn main() {
struct ByField<T, F> {
    item: T,
    key_fn: F,  // Function that extracts comparison key
}

impl<T, K: Ord, F: Fn(&T) -> K> Ord for ByField<T, F> {
    fn cmp(&self, other: &Self) -> Ordering {
        (self.key_fn)(&self.item).cmp(&(other.key_fn)(&other.item))
    }
}

// Usage: extract any field for comparison
let tasks = PriorityQueue::new();
tasks.push(ByField::new(task1, |t| t.priority));
tasks.push(ByField::new(task2, |t| t.deadline));
}

Reverse wrapper (invert ordering):

#![allow(unused)]
fn main() {
struct Reverse<T>(T);

impl<T: Ord> Ord for Reverse<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        other.0.cmp(&self.0)  // Swapped! Reverses ordering
    }
}

// Turn min-heap into max-heap:
let mut min_heap: PriorityQueue<i32, MinHeap> = PriorityQueue::new();
let mut max_heap: PriorityQueue<Reverse<i32>, MinHeap> = PriorityQueue::new();
}

Zero-cost: Wrappers compile away (same size as inner type).

7. Binary Heap Data Structure (Array-Based Tree)

Binary heap: Complete binary tree stored in an array using index arithmetic (no pointers).

Array-to-tree mapping:

Array:  [1, 3, 2, 7, 5, 6, 4]
Index:   0  1  2  3  4  5  6

Tree visualization (min-heap):
        1 (index 0)
       / \
      3   2  (indices 1, 2)
     / \ / \
    7  5 6  4  (indices 3, 4, 5, 6)

Parent of i:      (i - 1) / 2
Left child of i:  2 * i + 1
Right child of i: 2 * i + 2

Heap property:

Min-heap: Parent ≤ children (smallest at root)
Max-heap: Parent ≥ children (largest at root)

Why array representation?

No pointers: Cache-friendly, less memory
O(1) navigation: Parent/child index calculation is arithmetic
Cache locality: Children near parents in memory

Sift up (restore heap after insert):

#![allow(unused)]
fn main() {
fn sift_up(&mut self, mut i: usize) {
    while i > 0 {
        let parent = (i - 1) / 2;
        if self.heap[i] <= self.heap[parent] { break; }
        self.heap.swap(i, parent);
        i = parent;
    }
}
// Time: O(log n) - at most height of tree
}

Sift down (restore heap after pop):

#![allow(unused)]
fn main() {
fn sift_down(&mut self, mut i: usize) {
    loop {
        let left = 2 * i + 1;
        let right = 2 * i + 2;
        let mut largest = i;

        if left < len && self.heap[left] > self.heap[largest] {
            largest = left;
        }
        if right < len && self.heap[right] > self.heap[largest] {
            largest = right;
        }

        if largest == i { break; }
        self.heap.swap(i, largest);
        i = largest;
    }
}
// Time: O(log n)
}

8. Heapify Algorithm (O(n) Heap Construction)

Heapify: Build heap from unordered array in O(n) time (faster than O(n log n) repeated inserts).

Naive approach (repeated push):

#![allow(unused)]
fn main() {
let mut pq = PriorityQueue::new();
for item in items {  // N iterations
    pq.push(item);   // O(log n) each
}
// Total: O(n log n)
// For n=100,000: ~1.6 million operations
}

Floyd’s bottom-up heapify:

#![allow(unused)]
fn main() {
fn from_vec(mut vec: Vec<T>) -> Self {
    let last_parent = (vec.len() / 2).saturating_sub(1);

    // Sift down from last parent to root
    for i in (0..=last_parent).rev() {
        sift_down_from(&mut vec, i);
    }

    PriorityQueue { heap: vec, _order: PhantomData }
}
// Total: O(n)
// For n=100,000: ~100,000 operations (16× faster!)
}

Why O(n) instead of O(n log n)?

Intuition:

Leaves (half of nodes): Already valid heaps, do nothing (0 work)
Level h=1 (n/4 nodes): Sift down 1 step each (n/4 work)
Level h=2 (n/8 nodes): Sift down 2 steps each (n/4 work)
Level h=3 (n/16 nodes): Sift down 3 steps each (3n/16 work)
…

Total work: n/4 + n/4 + 3n/16 + … = O(n)

Mathematical proof:

Work = Σ (nodes at height h) × h
     = Σ (n / 2^(h+1)) × h
     = n × Σ h / 2^(h+1)
     = n × 2     (geometric series)
     = O(n)

9. FromIterator and IntoIterator Traits

FromIterator: Build collection from iterator (enables .collect()).

IntoIterator: Convert collection into iterator (enables for loops).

FromIterator:

#![allow(unused)]
fn main() {
trait FromIterator<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self;
}

impl<T: Ord, Order: HeapOrder> FromIterator<T> for PriorityQueue<T, Order> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let vec: Vec<T> = iter.into_iter().collect();
        Self::from_vec(vec)  // Uses O(n) heapify!
    }
}

// Now can use .collect():
let pq: PriorityQueue<i32> = vec![5, 3, 7, 1].into_iter().collect();

// Works with iterator chains:
let pq: PriorityQueue<i32> = data.into_iter()
    .filter(|x| x % 2 == 0)
    .map(|x| x * 2)
    .collect();  // Calls FromIterator::from_iter
}

IntoIterator:

#![allow(unused)]
fn main() {
trait IntoIterator {
    type Item;
    type IntoIter: Iterator<Item = Self::Item>;
    fn into_iter(self) -> Self::IntoIter;
}

impl<T: Ord, Order: HeapOrder> IntoIterator for PriorityQueue<T, Order> {
    type Item = T;
    type IntoIter = IntoIter<T, Order>;

    fn into_iter(self) -> Self::IntoIter {
        IntoIter { queue: self }
    }
}

struct IntoIter<T, Order> {
    queue: PriorityQueue<T, Order>,
}

impl<T: Ord, Order: HeapOrder> Iterator for IntoIter<T, Order> {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        self.queue.pop()  // Pop in sorted order!
    }
}

// Now works with for loops:
for item in pq {  // Calls into_iter(), then Iterator::next()
    println!("{}", item);
}
}

Why implement these traits?

Idiomatic Rust: Works like Vec, HashMap, BinaryHeap
Iterator chains: Compose with filter, map, take, etc.
Ergonomic API: Users expect .collect() and for loops to work

10. Zero-Cost Abstractions

Zero-cost abstractions: High-level abstractions compile to same code as hand-written low-level code.

Example: Generic code:

#![allow(unused)]
fn main() {
// Generic priority queue
fn process<T: Ord>(items: Vec<T>) {
    let mut pq: PriorityQueue<T> = PriorityQueue::from_vec(items);
    while let Some(item) = pq.pop() {
        // Process item
    }
}

// Compiler generates specialized code for each type:
process::<i32>(vec![1, 2, 3]);     // Generates i32 version
process::<String>(vec!["a".into()]);  // Generates String version

// Each specialization is as fast as if you hand-wrote:
fn process_i32(items: Vec<i32>) { ... }
fn process_string(items: Vec<String>) { ... }
}

Example: Phantom types:

#![allow(unused)]
fn main() {
let min: PriorityQueue<i32, MinHeap> = PriorityQueue::new();

// Compiles to:
fn sift_down_minheap(heap: &mut Vec<i32>, i: usize) {
    if heap[i] > heap[child] { swap }  // MinHeap logic inlined
}

let max: PriorityQueue<i32, MaxHeap> = PriorityQueue::new();

// Compiles to:
fn sift_down_maxheap(heap: &mut Vec<i32>, i: usize) {
    if heap[i] < heap[child] { swap }  // MaxHeap logic inlined
}

// PhantomData<Order> is zero bytes, completely optimized away!
}

Example: Wrapper types:

#![allow(unused)]
fn main() {
struct Reverse<T>(T);  // Newtype wrapper

// Compiles to same size and assembly as T itself:
assert_eq!(mem::size_of::<Reverse<i32>>(), mem::size_of::<i32>());
assert_eq!(mem::size_of::<Reverse<i32>>(), 4);  // Not 8 (no wrapper overhead!)
}

Measured performance (same as hand-written code):

Hand-written min-heap (C-style):  100ms
Generic PriorityQueue<T, MinHeap>: 100ms (same!)

Why zero-cost?

Monomorphization: Generates specialized code per type
Inlining: Small functions inlined at call sites
Dead code elimination: Unused code branches removed
Phantom types optimized away: PhantomData is zero bytes

Rust philosophy: “You don’t pay for what you don’t use.”

Connection to This Project

This project builds a production-quality generic priority queue, demonstrating how Rust’s generics enable zero-cost abstractions with compile-time safety.

Milestone 1: Basic Generic Structure with Vec Backend

Concepts applied:

Generic type parameters (PriorityQueue<T>)
Trait bounds (T: Ord)
Basic Vec operations

Why it matters: Starting with a naive sorted-Vec approach helps understand:

Generics fundamentals: <T> makes code reusable for any type
Trait bounds necessity: Can’t compare elements without T: Ord
Performance baseline: Naive O(n log n) sorting on every insert

Real-world impact:

#![allow(unused)]
fn main() {
// Naive approach: sort on every push
fn push(&mut self, item: T) {
    self.items.push(item);    // O(1)
    self.items.sort();         // O(n log n) - EXPENSIVE!
}

// For 1000-element queue:
// - Each insert: ~10,000 comparisons
// - Total for 1000 inserts: ~10 million comparisons
}

Performance comparison:

Operation	Naive (Milestone 1)	Proper Heap (Milestone 2)
Push	O(n log n) sort	O(log n) sift up
Pop	O(1)	O(log n) sift down
1000 inserts	10M comparisons	10K comparisons (1000× faster)

Why naive isn’t enough: Even moderate load (1000 events/sec) would spend 90% CPU sorting.

Milestone 2: Implement Binary Heap Structure (Sift Operations)

Concepts applied:

Binary heap data structure (array-based tree)
Index arithmetic (parent/child calculations)
Sift up and sift down algorithms
O(log n) operations

Why it matters: Binary heap provides efficient O(log n) operations:

Array representation: No pointers, cache-friendly
Sift up: After insert, bubble element up to restore heap property
Sift down: After pop, bubble root down to restore heap property

Real-world impact:

#![allow(unused)]
fn main() {
// Heap operations: O(log n)
fn push(&mut self, item: T) {
    self.heap.push(item);           // Add to end: O(1)
    self.sift_up(len - 1);          // Bubble up: O(log n)
}

fn pop(&mut self) -> Option<T> {
    self.heap.swap(0, len - 1);     // Move root to end: O(1)
    let result = self.heap.pop();   // Remove: O(1)
    self.sift_down(0);              // Bubble down: O(log n)
}

// For 10,000 elements:
// - Push: ~14 comparisons (vs 130,000 with naive)
// - Pop: ~14 comparisons
}

Performance comparison (10,000 elements):

Metric	Naive Sort	Binary Heap
Push time	130,000 comparisons	14 comparisons (9,000× faster)
Pop time	1 comparison	14 comparisons
Memory	Vec + sort buffer	Just Vec (20% less memory)

Real-world validation: std::collections::BinaryHeap uses same algorithm.

Milestone 3: Add Phantom Types for Min/Max Heap Variants

Concepts applied:

Phantom types (MinHeap, MaxHeap)
PhantomData (zero-sized types)
Compile-time dispatch via trait
Default type parameters

Why it matters: Phantom types enable compile-time ordering without code duplication:

Zero runtime cost: PhantomData<Order> is 0 bytes
Type safety: Can’t mix min-heap and max-heap operations
Single implementation: One codebase for both orderings

Real-world impact:

#![allow(unused)]
fn main() {
// WITHOUT phantom types (code duplication):
struct MinHeap<T> { heap: Vec<T> }
impl<T: Ord> MinHeap<T> {
    fn sift_down(&mut self, i: usize) {
        if self.heap[i] > self.heap[child] { swap }
    }
}

struct MaxHeap<T> { heap: Vec<T> }
impl<T: Ord> MaxHeap<T> {
    fn sift_down(&mut self, i: usize) {
        if self.heap[i] < self.heap[child] { swap }  // ONLY difference!
    }
}
// 500 lines duplicated!

// WITH phantom types (zero-cost abstraction):
struct PriorityQueue<T, Order = MinHeap> {
    heap: Vec<T>,
    _order: PhantomData<Order>,  // 0 bytes!
}

trait HeapOrder {
    fn should_swap<T: Ord>(parent: &T, child: &T) -> bool;
}

impl HeapOrder for MinHeap {
    fn should_swap<T: Ord>(parent: &T, child: &T) -> bool { parent > child }
}

impl HeapOrder for MaxHeap {
    fn should_swap<T: Ord>(parent: &T, child: &T) -> bool { parent < child }
}

// One implementation serves both!
impl<T: Ord, Order: HeapOrder> PriorityQueue<T, Order> {
    fn sift_down(&mut self, i: usize) {
        if Order::should_swap(&self.heap[i], &self.heap[child]) { swap }
    }
}
// 500 lines → 250 lines (50% less code!)
}

Size comparison:

Type	Size (bytes)
`Vec<i32>`	24
`PriorityQueue<i32, MinHeap>`	24 (same!)
`PhantomData<MinHeap>`	0

Compile-time dispatch (no runtime overhead):

#![allow(unused)]
fn main() {
let min: PriorityQueue<i32, MinHeap> = PriorityQueue::new();
// Compiler generates: if parent > child { swap }

let max: PriorityQueue<i32, MaxHeap> = PriorityQueue::new();
// Compiler generates: if parent < child { swap }
}

Benefits: 50% less code, zero runtime cost, type-safe.

Milestone 4: Support Custom Orderings with Wrapper Types

Concepts applied:

Newtype pattern (wrapper types)
Custom Ord implementations
Reverse wrapper for inverted ordering
Generic ByField wrapper for field extraction
Multi-field comparison with then()

Why it matters: Types have one natural Ord, but applications need different orderings:

Sort tasks by deadline vs priority
Min-heap vs max-heap for same type
Multi-field comparison (priority, then timestamp)

Wrapper types provide zero-cost custom orderings.

Real-world impact:

#![allow(unused)]
fn main() {
// WITHOUT wrappers (limited to one ordering):
struct Task {
    name: String,
    priority: u8,
    deadline: u64,
}

impl Ord for Task {
    fn cmp(&self, other: &Self) -> Ordering {
        self.name.cmp(&other.name)  // Only alphabetical ordering!
    }
}

let tasks: PriorityQueue<Task> = PriorityQueue::new();
// Stuck with alphabetical ordering

// WITH wrappers (flexible orderings):
struct ByPriority(Task);
impl Ord for ByPriority {
    fn cmp(&self, other: &Self) -> Ordering {
        self.0.priority.cmp(&other.0.priority)
    }
}

struct ByDeadline(Task);
impl Ord for ByDeadline {
    fn cmp(&self, other: &Self) -> Ordering {
        self.0.deadline.cmp(&other.0.deadline)
    }
}

// Now can choose ordering:
let by_priority: PriorityQueue<ByPriority> = PriorityQueue::new();
let by_deadline: PriorityQueue<ByDeadline> = PriorityQueue::new();
}

Generic wrapper (field extractor):

#![allow(unused)]
fn main() {
let tasks = PriorityQueue::new();
tasks.push(ByField::new(task, |t| t.priority));   // Sort by priority
tasks.push(ByField::new(task, |t| t.deadline));   // Sort by deadline
tasks.push(ByField::new(task, |t| t.name.len())); // Sort by name length!
}

Zero-cost proof:

#![allow(unused)]
fn main() {
assert_eq!(mem::size_of::<Reverse<i32>>(), mem::size_of::<i32>());
assert_eq!(mem::size_of::<Reverse<i32>>(), 4);  // Not 8!
}

Real-world use cases:

Dijkstra’s algorithm: Sort by distance (wrap (distance, node))
Event queue: Sort by timestamp (wrap events)
Task scheduler: Sort by deadline or priority
A search*: Sort by f-score (g + h heuristic)

Milestone 5: Implement Efficient Heapify (O(n) from Vec)

Concepts applied:

Floyd’s bottom-up heapify algorithm
O(n) heap construction (vs O(n log n))
Algorithmic optimization
Geometric series proof

Why it matters: Building heap from existing data is common:

Loading priority queue from file/database
Batch initialization
Converting sorted array to heap

Heapify is 16× faster than repeated push for large datasets.

Real-world impact:

#![allow(unused)]
fn main() {
// BEFORE heapify (naive push):
let mut pq = PriorityQueue::new();
for item in items {  // N iterations
    pq.push(item);   // O(log n) each
}
// Total: O(n log n)
// For n=100,000: ~1.6 million operations

// AFTER heapify (Floyd's algorithm):
let pq = PriorityQueue::from_vec(items);  // O(n)
// For n=100,000: ~100,000 operations (16× faster!)
}

Performance comparison (10,000 elements):

Method	Time	Operations
Repeated push	2.5ms	130,000 comparisons
Heapify	0.15ms	10,000 comparisons (16× faster)

Why O(n) works (geometric series):

Leaves (50% of nodes): 0 work each = 0
Level h=1 (25% of nodes): 1 step each = n/4
Level h=2 (12.5% of nodes): 2 steps each = n/4
Level h=3 (6.25% of nodes): 3 steps each = 3n/16
...
Total: n/4 + n/4 + 3n/16 + ... = 2n = O(n)

Real-world validation:

std::collections::BinaryHeap::from(): Uses heapify
Priority queue libraries: heapq.heapify() (Python), make_heap() (C++)
Dijkstra’s algorithm: Build initial heap from all nodes

Milestone 6: Add Iterator Support and Memory Optimizations

Concepts applied:

IntoIterator trait (enables for loops)
FromIterator trait (enables .collect())
Extend trait (add elements from iterator)
ExactSizeIterator (known length)
Memory management (with_capacity, reserve, shrink_to_fit)

Why it matters: Integration with Rust’s iterator ecosystem makes priority queue a first-class collection:

Idiomatic Rust: Works like Vec, HashMap, BinaryHeap
Iterator chains: Compose with filter, map, take
Memory control: Pre-allocate to avoid reallocations

Real-world impact:

#![allow(unused)]
fn main() {
// BEFORE iterator support:
let mut pq = PriorityQueue::new();
for item in data {
    pq.push(item);  // Manual loop
}

while let Some(item) = pq.pop() {
    process(item);  // Manual loop
}

// AFTER iterator support:
let pq: PriorityQueue<_> = data.into_iter()
    .filter(|x| x.is_valid())
    .map(|x| transform(x))
    .collect();  // FromIterator

for item in pq {  // IntoIterator
    process(item);
}
}

Memory optimization:

#![allow(unused)]
fn main() {
// WITHOUT pre-allocation:
let mut pq = PriorityQueue::new();  // Capacity: 0
for i in 0..10_000 {
    pq.push(i);  // Reallocates 14 times!
}
// Each reallocation copies entire heap

// WITH pre-allocation:
let mut pq = PriorityQueue::with_capacity(10_000);  // Capacity: 10,000
for i in 0..10_000 {
    pq.push(i);  // Zero reallocations!
}
}

Performance comparison (10,000 inserts):

Method	Time	Reallocations
Without capacity	0.8ms	14 reallocations
With capacity	0.5ms	0 reallocations (1.6× faster)

Iterator integration benefits:

Feature	Without Traits	With Traits
Build from iterator	Manual loop	`.collect()`
Consume queue	Manual `while let`	`for` loop
Iterator chains	Not possible	`filter().map().collect()`
Code size	Verbose	50% less code

Real-world use cases:

Data pipelines: stream.filter().map().collect() into queue
Batch processing: Load from file, process in priority order
Memory-constrained: Pre-allocate exact capacity

Implement a simple priority queue using Rust’s Vec<T> as the backing storage with a naive approach: sort on every insertion. This milestone focuses on understanding generic type parameters and trait bounds before optimizing for performance.

Why Start Simple?

Before building an efficient heap, we need to understand:

How generic type parameters work: <T> makes code reusable for any type
Why trait bounds matter: T: Ord ensures elements can be compared
How Rust’s ownership interacts with generic collections
The baseline performance to improve upon in later milestones

The Naive Approach:

#![allow(unused)]
fn main() {
// After each push:
items.push(new_element);
items.sort();  // O(n log n) - expensive!
}

This is inefficient but correct and easy to verify. Once tests pass, we can optimize.

Real-World Analogy:

Imagine a todo list where you write tasks on sticky notes. The naive approach is:

Add new task to bottom of pile
Sort entire pile every time
Take task from top

A proper heap would be: add task and bubble it to correct position (one path through the pile, not sorting everything).

Goal: Create a working priority queue using a Vec<T> with naive sorting.

struct: PriorityQueue<T> fields: items: Vec functions:

new() - Create empty queue
push(item: T) - Insert element (sift up to maintain heap property)
pop() -> Option<T> - Remove and return highest priority element (sift down)
peek() -> Option<&T> - View highest priority element
len(), is_empty() - Basic queries

Starter Code

#![allow(unused)]
fn main() {
pub struct PriorityQueue<T> {
    items: Vec<T>,
}

impl<T: Ord> PriorityQueue<T> {
    pub fn new() -> Self {
       todo!()
    }

    pub fn push(&mut self, item: T) {
       todo!()
    }

    pub fn pop(&mut self) -> Option<T> {
       todo!()  // Takes from end (highest priority after sorting)
    }

    pub fn peek(&self) -> Option<&T> {
        todo!()
    }

    pub fn len(&self) -> usize {
        todo!()

    pub fn is_empty(&self) -> bool {
       todo!()
    }
}
}

Checkpoint Tests:

#![allow(unused)]
fn main() {
#[test]
fn test_basic_push_pop_order() {
    let mut pq = PriorityQueue::new();

    // Insert in random order
    pq.push(5);
    pq.push(1);
    pq.push(3);
    pq.push(7);
    pq.push(2);

    // Should pop in sorted order (min-heap: smallest first)
    assert_eq!(pq.pop(), Some(7));
    assert_eq!(pq.pop(), Some(5));
    assert_eq!(pq.pop(), Some(3));
    assert_eq!(pq.pop(), Some(2));
    assert_eq!(pq.pop(), Some(1));
    assert_eq!(pq.pop(), None);
}

#[test]
fn test_with_different_types() {
    // Test with integers
    let mut int_queue = PriorityQueue::new();
    int_queue.push(10);
    int_queue.push(5);
    assert_eq!(int_queue.peek(), Some(&10));

    // Test with strings
    let mut string_queue = PriorityQueue::new();
    string_queue.push("zebra".to_string());
    string_queue.push("apple".to_string());
    string_queue.push("mango".to_string());

    assert_eq!(string_queue.pop(), Some("zebra".to_string()));
    assert_eq!(string_queue.pop(), Some("mango".to_string()));
    assert_eq!(string_queue.pop(), Some("apple".to_string()));
}

#[test]
fn test_custom_ord_type() {
    #[derive(Debug, PartialEq, Eq)]
    struct Task {
        priority: u32,
        name: String,
    }

    impl Ord for Task {
        fn cmp(&self, other: &Self) -> std::cmp::Ordering {
            self.priority.cmp(&other.priority)
        }
    }

    impl PartialOrd for Task {
        fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
            Some(self.cmp(other))
        }
    }

    let mut tasks = PriorityQueue::new();
    tasks.push(Task { priority: 5, name: "Medium".into() });
    tasks.push(Task { priority: 10, name: "High".into() });
    tasks.push(Task { priority: 1, name: "Low".into() });

    assert_eq!(tasks.pop().unwrap().priority, 10);
    assert_eq!(tasks.pop().unwrap().priority, 5);
    assert_eq!(tasks.pop().unwrap().priority, 1);
}

#[test]
fn test_peek_does_not_remove() {
    let mut pq = PriorityQueue::new();
    pq.push(42);
    pq.push(17);

    assert_eq!(pq.peek(), Some(&42));
    assert_eq!(pq.len(), 2);  // Still has both elements
    assert_eq!(pq.peek(), Some(&42));  // Can peek multiple times

    assert_eq!(pq.pop(), Some(42));
    assert_eq!(pq.len(), 1);
}

#[test]
fn test_empty_queue() {
    let mut pq: PriorityQueue<i32> = PriorityQueue::new();

    assert!(pq.is_empty());
    assert_eq!(pq.len(), 0);
    assert_eq!(pq.pop(), None);
    assert_eq!(pq.peek(), None);

    pq.push(1);
    assert!(!pq.is_empty());
    assert_eq!(pq.len(), 1);
}

#[test]
fn test_repeated_elements() {
    let mut pq = PriorityQueue::new();

    // Duplicate values should work
    pq.push(5);
    pq.push(5);
    pq.push(5);
    pq.push(3);

    assert_eq!(pq.pop(), Some(5));
    assert_eq!(pq.pop(), Some(5));
    assert_eq!(pq.pop(), Some(5));
    assert_eq!(pq.pop(), Some(3));
}
}

Why this isn’t enough:

The naive approach sorts the entire vector on every insertion, giving O(n log n) insertion time. For a priority queue processing thousands of events per second, this is unacceptable:

1,000-element queue: ~10,000 comparisons per insert (vs ~10 with a proper heap)
10,000 inserts: 100 million operations instead of 100,000
Real-world impact: A server processing 1000 events/sec would spend 90% CPU time just sorting

Performance comparison:

Naive: O(n log n) push, O(1) pop
Proper heap: O(log n) push, O(log n) pop

The naive approach becomes unusable with even moderate load. Next milestone implements efficient heap operations.

Milestone 2: Implement Binary Heap Structure (Sift Operations)

Replace the naive sorting approach with a proper binary heap data structure. A binary heap maintains a partial ordering where each parent node is less than (min-heap) or greater than (max-heap) its children, enabling O(log n) operations instead of O(n log n).

Why Binary Heap?

A binary heap is a complete binary tree stored in an array where:

Complete: All levels filled except possibly the last, which fills left-to-right
Heap property: Parent ≤ children (min-heap) or parent ≥ children (max-heap)
Array representation: No pointers needed, use index arithmetic

Key Insight - Array-Based Tree:

Array:  [1, 3, 2, 7, 5, 6, 4]
Indices: 0  1  2  3  4  5  6

Tree visualization:
        1 (index 0)
       / \
      3   2  (indices 1, 2)
     / \ / \
    7  5 6  4  (indices 3, 4, 5, 6)

Parent of i:      (i - 1) / 2
Left child of i:  2 * i + 1
Right child of i: 2 * i + 2

The Two Core Operations:

Sift Up (Bubble Up): After inserting at end, swap with parent if violates heap property
- Used by: push()
- Time: O(log n) - at most height of tree
Sift Down (Bubble Down): After removing root, move last element to root and swap down
- Used by: pop()
- Time: O(log n) - at most height of tree

Goal: Replace naive sorting with proper heap operations for O(log n) efficiency.

functions

sift_up(): bubble element at index i upward
sift down(): bubble element at index i downward

change push() and pop() to use the sift functions

What to improve: Starter Code

#![allow(unused)]
fn main() {
impl<T: Ord> PriorityQueue<T> {
    // Helper: Calculate parent index
    fn parent(i: usize) -> usize {
        todo!()
    }

    // Helper: Calculate left child index
    fn left_child(i: usize) -> usize {
        todo!()
    }

    // Helper: Calculate right child index
    fn right_child(i: usize) -> usize {
       todo!()
    }

    // Sift up: bubble element at index i upward to restore heap property
    fn sift_up(&mut self, mut i: usize) {
        todo!()
    }

    // Sift down: bubble element at index i downward to restore heap property
    fn sift_down(&mut self, mut i: usize) {
        loop {
            let left = Self::left_child(i);
            let right = Self::right_child(i);
            
            todo!()
        }
    }

    pub fn push(&mut self, item: T) { 
        todo!()        // Restore heap property: 
    }

    pub fn pop(&mut self) -> Option<T> {
        todo!()
    }
}
}

Checkpoint Tests:

#![allow(unused)]
fn main() {
#[test]
fn test_heap_property_maintained() {
    let mut pq = PriorityQueue::new();

    // Insert elements
    for &val in &[5, 3, 7, 1, 9, 4, 8] {
        pq.push(val);
        assert!(verify_heap_property(&pq));
    }

    // Pop elements
    while !pq.is_empty() {
        pq.pop();
        assert!(verify_heap_property(&pq));
    }
}

// Helper function to verify heap property
fn verify_heap_property<T: Ord>(pq: &PriorityQueue<T>) -> bool {
    for i in 0..pq.len() {
        let left = 2 * i + 1;
        let right = 2 * i + 2;

        if left < pq.len() && pq.items[i] < pq.items[left] {
            return false;  // Parent should be >= left child
        }
        if right < pq.len() && pq.items[i] < pq.items[right] {
            return false;  // Parent should be >= right child
        }
    }
    true
}

#[test]
fn test_sift_operations_correctness() {
    let mut pq = PriorityQueue::new();

    // Build heap: [9, 7, 8, 3, 5, 4]
    //        9
    //       / \
    //      7   8
    //     / \ /
    //    3  5 4

    pq.push(5);
    pq.push(3);
    pq.push(7);
    pq.push(1);
    pq.push(9);
    pq.push(4);
    pq.push(8);

    // Verify largest is at root
    assert_eq!(pq.peek(), Some(&9));

    // Pop should give sorted order
    assert_eq!(pq.pop(), Some(9));
    assert_eq!(pq.pop(), Some(8));
    assert_eq!(pq.pop(), Some(7));
    assert_eq!(pq.pop(), Some(5));
    assert_eq!(pq.pop(), Some(4));
    assert_eq!(pq.pop(), Some(3));
    assert_eq!(pq.pop(), Some(1));
}

#[test]
fn test_large_dataset() {
    let mut pq = PriorityQueue::new();

    // Insert 10,000 elements in random order
    for i in 0..10_000 {
        pq.push(i * 7 % 10_000);  // Pseudo-random order
    }

    // Pop all and verify sorted
    let mut prev = pq.pop().unwrap();
    for _ in 1..10_000 {
        let curr = pq.pop().unwrap();
        assert!(curr <= prev);  // Descending order (max-heap)
        prev = curr;
    }
}

#[test]
fn test_performance_vs_naive() {
    use std::time::Instant;

    let size = 1000;

    // Measure heap-based (this implementation)
    let start = Instant::now();
    let mut heap_pq = PriorityQueue::new();
    for i in 0..size {
        heap_pq.push(i);
    }
    let heap_time = start.elapsed();

    // For comparison (don't actually run in tests, but conceptually):
    // Naive would be: size * size * log(size) / 2 comparisons
    // Heap is:        size * log(size) comparisons
    // Expected speedup: ~size / 2

    println!("Heap insertion time for {}: {:?}", size, heap_time);
    assert!(heap_pq.len() == size);
}

#[test]
fn test_heap_index_arithmetic() {
    // Verify helper functions work correctly
    assert_eq!(PriorityQueue::<i32>::parent(1), 0);
    assert_eq!(PriorityQueue::<i32>::parent(2), 0);
    assert_eq!(PriorityQueue::<i32>::parent(3), 1);
    assert_eq!(PriorityQueue::<i32>::parent(4), 1);
    assert_eq!(PriorityQueue::<i32>::parent(5), 2);

    assert_eq!(PriorityQueue::<i32>::left_child(0), 1);
    assert_eq!(PriorityQueue::<i32>::left_child(1), 3);
    assert_eq!(PriorityQueue::<i32>::left_child(2), 5);

    assert_eq!(PriorityQueue::<i32>::right_child(0), 2);
    assert_eq!(PriorityQueue::<i32>::right_child(1), 4);
    assert_eq!(PriorityQueue::<i32>::right_child(2), 6);
}

#[test]
fn test_single_element() {
    let mut pq = PriorityQueue::new();
    pq.push(42);

    assert_eq!(pq.peek(), Some(&42));
    assert_eq!(pq.pop(), Some(42));
    assert_eq!(pq.pop(), None);
}

#[test]
fn test_two_elements() {
    let mut pq = PriorityQueue::new();
    pq.push(10);
    pq.push(20);

    assert_eq!(pq.pop(), Some(20));
    assert_eq!(pq.pop(), Some(10));
}
}

Why this isn’t enough:

We’re limited to natural ordering (T: Ord). This implementation always creates a max-heap (largest element at root). But real applications need flexibility:

Min-heap: Process smallest/earliest items first (event queue, Dijkstra’s algorithm)
Max-heap: Process largest/latest items first (top-K problems)
Custom ordering: Prioritize by deadline, not insertion time; by severity, not timestamp

The current design can’t handle these without code duplication (copying the entire implementation for min-heap vs max-heap). We need a way to parameterize the comparison logic at compile-time—that’s what phantom types solve in Milestone 3.

Milestone 3: Add Phantom Types for Min/Max Heap Variants

Use phantom types to parameterize the heap ordering strategy at compile time. This allows the same code to work as either a min-heap or max-heap without runtime overhead or code duplication.

Why Phantom Types?

Phantom types are zero-sized type parameters that exist only at compile time:

Zero runtime cost: PhantomData<T> is 0 bytes, optimized away completely
Compile-time dispatch: Compiler generates different code for MinHeap vs MaxHeap
Type safety: Can’t accidentally mix min-heap and max-heap operations
No code duplication: Single implementation serves both orderings

The Problem With Current Design:

#![allow(unused)]
fn main() {
// Milestone 2: Hardcoded max-heap
if self.items[left] > self.items[largest] { ... }  // Always >

// To support min-heap, we'd need to duplicate entire impl:
if self.items[left] < self.items[smallest] { ... }  // Always <
}

This violates DRY (Don’t Repeat Yourself) and creates maintenance burden.

The Phantom Type Solution:

#![allow(unused)]
fn main() {
// Marker types (zero-sized)
struct MinHeap;
struct MaxHeap;

// Generic over ordering
struct PriorityQueue<T, Order = MinHeap> {
    heap: Vec<T>,
    _order: PhantomData<Order>,  // 0 bytes!
}

// Trait defines ordering behavior
trait HeapOrder {
    fn should_swap<T: Ord>(parent: &T, child: &T) -> bool;
}

// Different impls for different orderings
impl HeapOrder for MinHeap {
    fn should_swap<T: Ord>(parent: &T, child: &T) -> bool {
        parent > child  // Parent should be ≤ child
    }
}
}

Now one implementation handles both cases via compile-time polymorphism.

Real-World Analogy:

Think of a sorting machine with interchangeable comparator modules:

MinHeap module: “Is left > right?” → swap
MaxHeap module: “Is left < right?” → swap

Same machine (code), different module (type parameter), but the module is just a label—it weighs nothing!

Goal: Use phantom types to support both min-heap and max-heap at compile time.

What to improve:

Starter Code

#![allow(unused)]
fn main() {
use std::marker::PhantomData;
use std::cmp::Ordering;

// Marker types for ordering


// Trait defining heap ordering behavior
pub trait HeapOrder {
    fn should_swap<T: Ord>(parent: &T, child: &T) -> bool;
}

impl HeapOrder for MinHeap {
    fn should_swap<T: Ord>(parent: &T, child: &T) -> bool {
        //TODO: Min heap: parent should be ≤ child
    }
}

impl HeapOrder for MaxHeap {
    fn should_swap<T: Ord>(parent: &T, child: &T) -> bool {
        // TODO: Max heap: parent should be ≥ child
    }
}

// Generic priority queue with default ordering
pub struct PriorityQueue<T, Order = MinHeap> {
    heap: Vec<T>,
    _order: PhantomData<Order>,
}

impl<T: Ord, Order: HeapOrder> PriorityQueue<T, Order> {
    pub fn new() -> Self {
        PriorityQueue {
            heap: Vec::new(),
            _order: PhantomData,
        }
    }

    fn parent(i: usize) -> usize {
        (i - 1) / 2
    }

    fn left_child(i: usize) -> usize {
        2 * i + 1
    }

    fn right_child(i: usize) -> usize {
        2 * i + 2
    }

    fn sift_up(&mut self, mut i: usize) {
        while i > 0 {
            let parent = Self::parent(i);
            // TODO: Use HeapOrder trait instead of hardcoded comparison
           
        }
    }

    fn sift_down(&mut self, mut i: usize) {
        loop {
            let left = Self::left_child(i);
            let right = Self::right_child(i);
            let mut swap_with = i;

            // TODO: Use HeapOrder trait instead of hardcoded comparison

            if swap_with == i {
                break;
            }

            self.heap.swap(i, swap_with);
            i = swap_with;
        }
    }

    pub fn push(&mut self, item: T) {
       todo!()
    }

    pub fn pop(&mut self) -> Option<T> {
        todo!()
    }

    pub fn peek(&self) -> Option<&T> {
        self.heap.first()
    }

    pub fn len(&self) -> usize {
        self.heap.len()
    }

    pub fn is_empty(&self) -> bool {
        self.heap.is_empty()
    }
}
}

Checkpoint Tests:

#![allow(unused)]
fn main() {
#[test]
fn test_min_heap_ordering() {
    let mut min_heap: PriorityQueue<i32, MinHeap> = PriorityQueue::new();

    min_heap.push(5);
    min_heap.push(3);
    min_heap.push(7);
    min_heap.push(1);
    min_heap.push(9);

    // Min heap: smallest first
    assert_eq!(min_heap.pop(), Some(1));
    assert_eq!(min_heap.pop(), Some(3));
    assert_eq!(min_heap.pop(), Some(5));
    assert_eq!(min_heap.pop(), Some(7));
    assert_eq!(min_heap.pop(), Some(9));
}

#[test]
fn test_max_heap_ordering() {
    let mut max_heap: PriorityQueue<i32, MaxHeap> = PriorityQueue::new();

    max_heap.push(5);
    max_heap.push(3);
    max_heap.push(7);
    max_heap.push(1);
    max_heap.push(9);

    // Max heap: largest first
    assert_eq!(max_heap.pop(), Some(9));
    assert_eq!(max_heap.pop(), Some(7));
    assert_eq!(max_heap.pop(), Some(5));
    assert_eq!(max_heap.pop(), Some(3));
    assert_eq!(max_heap.pop(), Some(1));
}

#[test]
fn test_default_is_min_heap() {
    // Without specifying Order, should default to MinHeap
    let mut pq: PriorityQueue<i32> = PriorityQueue::new();

    pq.push(10);
    pq.push(5);
    pq.push(15);

    assert_eq!(pq.pop(), Some(5));  // Smallest first
}

#[test]
fn test_phantom_data_zero_size() {
    use std::mem;

    // PhantomData should add zero bytes
    assert_eq!(
        mem::size_of::<PriorityQueue<i32, MinHeap>>(),
        mem::size_of::<Vec<i32>>()  // Same size as Vec alone
    );

    assert_eq!(
        mem::size_of::<PhantomData<MinHeap>>(),
        0
    );
}

#[test]
fn test_min_heap_with_strings() {
    let mut pq: PriorityQueue<String, MinHeap> = PriorityQueue::new();

    pq.push("zebra".to_string());
    pq.push("apple".to_string());
    pq.push("mango".to_string());
    pq.push("banana".to_string());

    // Lexicographic order: smallest first
    assert_eq!(pq.pop(), Some("apple".to_string()));
    assert_eq!(pq.pop(), Some("banana".to_string()));
    assert_eq!(pq.pop(), Some("mango".to_string()));
    assert_eq!(pq.pop(), Some("zebra".to_string()));
}

#[test]
fn test_max_heap_with_strings() {
    let mut pq: PriorityQueue<String, MaxHeap> = PriorityQueue::new();

    pq.push("zebra".to_string());
    pq.push("apple".to_string());
    pq.push("mango".to_string());

    // Lexicographic order: largest first
    assert_eq!(pq.pop(), Some("zebra".to_string()));
    assert_eq!(pq.pop(), Some("mango".to_string()));
    assert_eq!(pq.pop(), Some("apple".to_string()));
}

#[test]
fn test_type_safety() {
    let _min: PriorityQueue<i32, MinHeap> = PriorityQueue::new();
    let _max: PriorityQueue<i32, MaxHeap> = PriorityQueue::new();

    // These are different types - can't accidentally mix
    // Uncommenting this would cause compile error:
    // let mixed: PriorityQueue<i32, MinHeap> = _max;
}

#[test]
fn test_peek_respects_ordering() {
    let mut min_heap: PriorityQueue<i32, MinHeap> = PriorityQueue::new();
    min_heap.push(10);
    min_heap.push(5);
    min_heap.push(15);

    assert_eq!(min_heap.peek(), Some(&5));  // Smallest at top

    let mut max_heap: PriorityQueue<i32, MaxHeap> = PriorityQueue::new();
    max_heap.push(10);
    max_heap.push(5);
    max_heap.push(15);

    assert_eq!(max_heap.peek(), Some(&15));  // Largest at top
}
}

Why this isn’t enough:

Phantom types solve the min/max problem elegantly, but they’re limited to scenarios where we can define ordering at the type level. Real-world applications often need:

Custom priorities: Sort tasks by deadline field, not natural Ord of the struct
Multi-field comparison: Priority by (severity, then timestamp)
Runtime-configurable ordering: User selects sorting criteria at runtime
Wrapper-based ordering: Turn max-heap into min-heap by wrapping values

The next milestone solves this with wrapper types that implement custom Ord.

Milestone 4: Support Custom Orderings with Wrapper Types

Enable custom comparison strategies by wrapping elements in types that implement their own Ord. This allows sorting by specific fields, reversing orderings, or applying complex multi-criteria comparisons—all while keeping the priority queue implementation unchanged.

Why Wrapper Types?

The priority queue works with any T: Ord, so we can:

Wrap values in types with custom Ord implementations
Let the heap use its normal comparison logic
Unwrap values when popping

This is the newtype pattern: zero-cost abstraction that changes type-level behavior.

The Custom Ordering Problem:

#![allow(unused)]
fn main() {
struct Task {
    name: String,
    priority: u8,
    deadline: u64,
}

// Default Ord might compare by name (alphabetical)
// But we want to compare by deadline!
}

Without wrapper types, we’d need to:

Modify Task’s Ord implementation (but what if different parts of code need different orderings?)
Create separate PriorityQueue implementations (code duplication!)

The Wrapper Type Solution:

#![allow(unused)]
fn main() {
// Wrapper changes how comparison works
struct ByDeadline(Task);

impl Ord for ByDeadline {
    fn cmp(&self, other: &Self) -> Ordering {
        self.0.deadline.cmp(&other.0.deadline)  // Compare by field!
    }
}

// Now can use with standard PriorityQueue
let mut tasks: PriorityQueue<ByDeadline> = PriorityQueue::new();
}

Real-World Analogy:

Think of documents in filing cabinets:

Default order: Alphabetical by title
Reverse wrapper: Put “Z” documents at front
ByDate wrapper: Ignore title, sort by date field
ByPriority wrapper: Urgent documents first

Same documents, same filing system, just different comparison rules.

Goal: Allow custom comparison strategies while maintaining type safety.

Starter Code

#![allow(unused)]
fn main() {
use std::cmp::Ordering;

// 1. Reverse wrapper - inverts natural ordering
// TODO: #[derive(..)]
pub struct Reverse<T>(pub T);

impl<T: Ord> Ord for Reverse<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        todo!()
    }
}

impl<T: PartialOrd> PartialOrd for Reverse<T> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        todo!()
    }
}

// 2. Priority by field - extract key for comparison
// TODO: #[derive(..)]
pub struct ByField<T, F> {
    pub item: T,
    key_fn: F,
}

impl<T, F> ByField<T, F> {
    pub fn new(item: T, key_fn: F) -> Self {
       todo!()
    }
}

impl<T, K: Ord, F: Fn(&T) -> K> Ord for ByField<T, F> {
    fn cmp(&self, other: &Self) -> Ordering {
        todo!()
    }
}

impl<T, K: Ord, F: Fn(&T) -> K> PartialOrd for ByField<T, F> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        todo!()
    }
}

impl<T, K: Eq, F: Fn(&T) -> K> Eq for ByField<T, F> {}

impl<T, K: Eq, F: Fn(&T) -> K> PartialEq for ByField<T, F> {
    fn eq(&self, other: &Self) -> bool {
        todo!()
    }
}

// 3. Example: Task with multiple fields
// TODO: #[derive(..)]
pub struct Task {
    pub name: String,
    pub priority: u8,
    pub deadline: u64,
}

// Default Ord: lexicographic by name
impl Ord for Task {
    fn cmp(&self, other: &Self) -> Ordering {
        todo!()
    }
}

impl PartialOrd for Task {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        todo!()
    }
}
}

Checkpoint Tests:

#![allow(unused)]
fn main() {
#[test]
fn test_reverse_wrapper() {
    let mut pq: PriorityQueue<Reverse<i32>, MinHeap> = PriorityQueue::new();

    pq.push(Reverse(5));
    pq.push(Reverse(3));
    pq.push(Reverse(7));
    pq.push(Reverse(1));

    // MinHeap with Reverse: largest first (like MaxHeap)
    assert_eq!(pq.pop().unwrap().0, 7);
    assert_eq!(pq.pop().unwrap().0, 5);
    assert_eq!(pq.pop().unwrap().0, 3);
    assert_eq!(pq.pop().unwrap().0, 1);
}

#[test]
fn test_task_by_priority() {
    let mut tasks: PriorityQueue<ByField<Task, _>, MinHeap> = PriorityQueue::new();

    tasks.push(ByField::new(
        Task { name: "Low".into(), priority: 1, deadline: 100 },
        |t| t.priority
    ));
    tasks.push(ByField::new(
        Task { name: "High".into(), priority: 10, deadline: 50 },
        |t| t.priority
    ));
    tasks.push(ByField::new(
        Task { name: "Medium".into(), priority: 5, deadline: 75 },
        |t| t.priority
    ));

    // Should pop in priority order: 1, 5, 10
    assert_eq!(tasks.pop().unwrap().item.priority, 1);
    assert_eq!(tasks.pop().unwrap().item.priority, 5);
    assert_eq!(tasks.pop().unwrap().item.priority, 10);
}

#[test]
fn test_task_by_deadline() {
    let mut tasks: PriorityQueue<ByField<Task, _>, MinHeap> = PriorityQueue::new();

    tasks.push(ByField::new(
        Task { name: "Later".into(), priority: 10, deadline: 200 },
        |t| t.deadline
    ));
    tasks.push(ByField::new(
        Task { name: "Soon".into(), priority: 1, deadline: 50 },
        |t| t.deadline
    ));
    tasks.push(ByField::new(
        Task { name: "Middle".into(), priority: 5, deadline: 100 },
        |t| t.deadline
    ));

    // Should pop by earliest deadline: 50, 100, 200
    assert_eq!(tasks.pop().unwrap().item.deadline, 50);
    assert_eq!(tasks.pop().unwrap().item.deadline, 100);
    assert_eq!(tasks.pop().unwrap().item.deadline, 200);
}

#[test]
fn test_multi_field_comparison() {
    #[derive(Debug, Clone, Eq, PartialEq)]
    struct Event {
        severity: u8,  // Higher = more severe
        timestamp: u64,
    }

    impl Ord for Event {
        fn cmp(&self, other: &Self) -> Ordering {
            // Compare by severity first (reversed: high severity first)
            // Then by timestamp (early first)
            other.severity.cmp(&self.severity)
                .then(self.timestamp.cmp(&other.timestamp))
        }
    }

    impl PartialOrd for Event {
        fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
            Some(self.cmp(other))
        }
    }

    let mut events: PriorityQueue<Event, MinHeap> = PriorityQueue::new();

    events.push(Event { severity: 5, timestamp: 100 });
    events.push(Event { severity: 10, timestamp: 50 });  // Highest severity
    events.push(Event { severity: 10, timestamp: 75 });  // Same severity, later time
    events.push(Event { severity: 3, timestamp: 25 });

    // Should pop: (10, 50), (10, 75), (5, 100), (3, 25)
    let e1 = events.pop().unwrap();
    assert_eq!((e1.severity, e1.timestamp), (10, 50));

    let e2 = events.pop().unwrap();
    assert_eq!((e2.severity, e2.timestamp), (10, 75));

    let e3 = events.pop().unwrap();
    assert_eq!((e3.severity, e3.timestamp), (5, 100));

    let e4 = events.pop().unwrap();
    assert_eq!((e4.severity, e4.timestamp), (3, 25));
}

#[test]
fn test_reverse_with_custom_type() {
    let mut tasks: PriorityQueue<Reverse<Task>, MinHeap> = PriorityQueue::new();

    tasks.push(Reverse(Task { name: "A".into(), priority: 1, deadline: 100 }));
    tasks.push(Reverse(Task { name: "Z".into(), priority: 1, deadline: 100 }));
    tasks.push(Reverse(Task { name: "M".into(), priority: 1, deadline: 100 }));

    // Reversed alphabetical order
    assert_eq!(tasks.pop().unwrap().0.name, "Z");
    assert_eq!(tasks.pop().unwrap().0.name, "M");
    assert_eq!(tasks.pop().unwrap().0.name, "A");
}

#[test]
fn test_wrapper_zero_cost() {
    use std::mem;

    // Wrapper should add no overhead
    assert_eq!(
        mem::size_of::<Reverse<i32>>(),
        mem::size_of::<i32>()
    );

    assert_eq!(
        mem::size_of::<Reverse<String>>(),
        mem::size_of::<String>()
    );
}

#[test]
fn test_chained_wrappers() {
    // Can combine wrappers for complex behavior
    let mut pq: PriorityQueue<Reverse<ByField<Task, _>>, MinHeap> = PriorityQueue::new();

    pq.push(Reverse(ByField::new(
        Task { name: "Low".into(), priority: 1, deadline: 100 },
        |t| t.priority
    )));
    pq.push(Reverse(ByField::new(
        Task { name: "High".into(), priority: 10, deadline: 50 },
        |t| t.priority
    )));

    // Reversed priority: highest first
    assert_eq!(pq.pop().unwrap().0.item.priority, 10);
    assert_eq!(pq.pop().unwrap().0.item.priority, 1);
}
}

Why this isn’t enough:

Building a heap from an existing collection currently requires pushing N elements one at a time:

#![allow(unused)]
fn main() {
let mut pq = PriorityQueue::new();
for item in items {
    pq.push(item);  // N × O(log n) = O(n log n)
}
}

For 100,000 items, this does ~1.6 million comparisons. There’s a more efficient heapify algorithm that builds a heap in O(n) using only ~100,000 comparisons—a 16× improvement! This is critical for bulk initialization from existing data.

Milestone 5: Implement Efficient Heapify (O(n) from Vec)

Implement Floyd’s bottom-up heapify algorithm to build a heap from an existing Vec<T> in O(n) time instead of O(n log n). This is critical for performance when initializing a priority queue from a large dataset.

Why Heapify Matters:

Building a heap by pushing N elements one-at-a-time:

#![allow(unused)]
fn main() {
for item in items {  // N iterations
    pq.push(item);   // O(log n) each
}
// Total: O(n log n)
}

For N=100,000: ~1.6 million operations

Bottom-up heapify:

#![allow(unused)]
fn main() {
PriorityQueue::from_vec(items)  // O(n)
}

For N=100,000: ~100,000 operations (16× faster!)

Floyd’s Algorithm Intuition:

Instead of inserting elements one by one from the top (sift up), start from the bottom and fix parents (sift down):

Leaves are already valid heaps (half the elements!)
Work up from last parent, fixing each subtree
Each level needs fewer ops: Bottom does nothing, middle does O(n/4), top does O(n/8)…

Mathematical proof of O(n):

Level h (from bottom): n/(2^(h+1)) nodes, each sifts down h steps
Total work: Σ h · n/(2^(h+1)) = n · Σ h/(2^(h+1))
          = n · [1/2 + 2/4 + 3/8 + 4/16 + ...]
          = n · 2     (geometric series)
          = O(n)

Goal: Add efficient bulk construction from existing data.

Add function:

from_vec() Starter Code:

#![allow(unused)]
fn main() {
impl<T: Ord, Order: HeapOrder> PriorityQueue<T, Order> {
    /// Build heap from existing vector in O(n) time
   Self {
        todo!();
    }

    /// Sift down element at index i (standalone version for heapify)
    fn sift_down_from(heap: &mut Vec<T>, mut i: usize) {
       todo!()
    }
}
}

Checkpoint Test

#![allow(unused)]
fn main() {
#[test]
fn test_from_vec_correctness() {
    let vec = vec![5, 3, 7, 1, 9, 4, 8, 2, 6];
    let mut pq: PriorityQueue<i32, MinHeap> = PriorityQueue::from_vec(vec);

    // Should produce sorted sequence
    assert_eq!(pq.pop(), Some(1));
    assert_eq!(pq.pop(), Some(2));
    assert_eq!(pq.pop(), Some(3));
    assert_eq!(pq.pop(), Some(4));
    assert_eq!(pq.pop(), Some(5));
    assert_eq!(pq.pop(), Some(6));
    assert_eq!(pq.pop(), Some(7));
    assert_eq!(pq.pop(), Some(8));
    assert_eq!(pq.pop(), Some(9));
}

#[test]
fn test_from_vec_performance() {
    use std::time::Instant;

    let size = 10_000;
    let data: Vec<i32> = (0..size).rev().collect();  // Worst case: reverse sorted

    // Method 1: from_vec (heapify)
    let data1 = data.clone();
    let start = Instant::now();
    let pq1: PriorityQueue<i32, MinHeap> = PriorityQueue::from_vec(data1);
    let heapify_time = start.elapsed();

    // Method 2: repeated push
    let start = Instant::now();
    let mut pq2: PriorityQueue<i32, MinHeap> = PriorityQueue::new();
    for item in data {
        pq2.push(item);
    }
    let push_time = start.elapsed();

    println!("Heapify: {:?}, Push: {:?}", heapify_time, push_time);
    println!("Speedup: {:.2}x", push_time.as_secs_f64() / heapify_time.as_secs_f64());

    // Both should produce same result
    assert_eq!(pq1.len(), pq2.len());
}

#[test]
fn test_from_vec_maintains_heap_property() {
    let vec = vec![15, 3, 17, 10, 84, 19, 6, 22, 9];
    let pq: PriorityQueue<i32, MinHeap> = PriorityQueue::from_vec(vec);

    // Verify heap property
    for i in 0..pq.len() {
        let left = 2 * i + 1;
        let right = 2 * i + 2;

        if left < pq.len() {
            assert!(pq.heap[i] <= pq.heap[left], "Parent {} > left child {}", pq.heap[i], pq.heap[left]);
        }
        if right < pq.len() {
            assert!(pq.heap[i] <= pq.heap[right], "Parent {} > right child {}", pq.heap[i], pq.heap[right]);
        }
    }
}

#[test]
fn test_from_vec_empty() {
    let vec: Vec<i32> = vec![];
    let pq: PriorityQueue<i32, MinHeap> = PriorityQueue::from_vec(vec);

    assert!(pq.is_empty());
    assert_eq!(pq.pop(), None);
}

#[test]
fn test_from_vec_single_element() {
    let vec = vec![42];
    let mut pq: PriorityQueue<i32, MinHeap> = PriorityQueue::from_vec(vec);

    assert_eq!(pq.len(), 1);
    assert_eq!(pq.pop(), Some(42));
}

#[test]
fn test_from_vec_with_max_heap() {
    let vec = vec![5, 3, 7, 1, 9, 4, 8];
    let mut pq: PriorityQueue<i32, MaxHeap> = PriorityQueue::from_vec(vec);

    // Max heap: largest first
    assert_eq!(pq.pop(), Some(9));
    assert_eq!(pq.pop(), Some(8));
    assert_eq!(pq.pop(), Some(7));
}

#[test]
fn test_from_vec_large_dataset() {
    let size = 100_000;
    let vec: Vec<i32> = (0..size).collect();

    let pq: PriorityQueue<i32, MinHeap> = PriorityQueue::from_vec(vec);

    assert_eq!(pq.len(), size as usize);
    assert_eq!(pq.peek(), Some(&0));
}
}

Why this isn’t enough:

Performance is good, but integration with Rust’s ecosystem is missing:

#![allow(unused)]
fn main() {
// Can't do this yet:
let pq: PriorityQueue<_> = values.iter()
    .filter(|x| x.is_valid())
    .map(|x| x.priority_score())
    .collect();  // ❌ No FromIterator impl

// Can't do this yet:
for item in pq {  // ❌ No IntoIterator impl
    println!("{}", item);
}
}

Also missing:

Memory control: Can’t pre-allocate capacity
Streaming construction: Must collect entire Vec first
Partial consumption: Can’t drain elements without consuming entire queue

Next milestone adds full iterator support and memory management.

Milestone 6: Add Iterator Support and Memory Optimizations

Integrate the priority queue with Rust’s iterator ecosystem and add memory management methods. This makes it a first-class collection that works seamlessly with iterator chains, collect(), and for loops.

Why Iterator Integration Matters:

Rust’s iterator ecosystem is powerful but requires explicit trait implementations:

#![allow(unused)]
fn main() {
// Want to write this:
let pq: PriorityQueue<_> = data.into_iter()
    .filter(|x| x.is_valid())
    .map(|x| transform(x))
    .collect();  // Needs FromIterator

// And this:
for item in pq {  // Needs IntoIterator
    process(item);
}
}

Without these traits, users must write manual loops—verbose and unidiomatic.

Memory Management:

Pre-allocation prevents reallocations during growth:

Without with_capacity: Push 10,000 items → 14 reallocations (copy entire heap each time!)
With with_capacity(10_000): Push 10,000 items → 0 reallocations

Goal: Make the priority queue work with Rust’s iterator ecosystem and optimize memory usage. Starter Code

#![allow(unused)]
fn main() {
// 1. IntoIterator - consume queue, iterate in sorted order
impl<T, Order> IntoIterator for PriorityQueue<T, Order>
where
    T: Ord,
    Order: HeapOrder,
{
    type Item = T;
    type IntoIter = IntoIter<T, Order>;

    fn into_iter(self) -> Self::IntoIter {
       todo!()
    }
}

pub struct IntoIter<T, Order> {
    queue: PriorityQueue<T, Order>,
}

impl<T: Ord, Order: HeapOrder> Iterator for IntoIter<T, Order> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
      todo!()
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
       todo!()
    }
}

impl<T: Ord, Order: HeapOrder> ExactSizeIterator for IntoIter<T, Order> {}

// 2. FromIterator - build queue from iterator
impl<T: Ord, Order: HeapOrder> FromIterator<T> for PriorityQueue<T, Order> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
       todo!()
}

// 3. Extend - add elements from iterator
impl<T: Ord, Order: HeapOrder> Extend<T> for PriorityQueue<T, Order> {
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        todo!()
        // Could optimize: collect, heapify, then merge
    }
}

// 4. Memory management
impl<T: Ord, Order: HeapOrder> PriorityQueue<T, Order> {
    /// Create with pre-allocated capacity
    pub fn with_capacity(capacity: usize) -> Self {
      todo!()
    }

    /// Current capacity (allocated space)
    pub fn capacity(&self) -> usize {
        todo!()
    }

    /// Reserve space for at least `additional` more elements
    pub fn reserve(&mut self, additional: usize) {
       todo!()
    }

    /// Shrink capacity to fit current length
    pub fn shrink_to_fit(&mut self) {
        todo!()
    }

    /// Remove all elements
    pub fn clear(&mut self) {
        todo!()
    }
}
}

Checkpoint Tests:

#![allow(unused)]
fn main() {
#[test]
fn test_into_iter_sorted_order() {
    let mut pq: PriorityQueue<i32, MinHeap> = PriorityQueue::new();

    pq.push(5);
    pq.push(3);
    pq.push(7);
    pq.push(1);
    pq.push(9);

    let result: Vec<i32> = pq.into_iter().collect();
    assert_eq!(result, vec![1, 3, 5, 7, 9]);
}

#[test]
fn test_from_iterator() {
    let data = vec![5, 3, 7, 1, 9, 4, 8];

    let pq: PriorityQueue<i32, MinHeap> = data.into_iter().collect();

    assert_eq!(pq.len(), 7);
    assert_eq!(pq.peek(), Some(&1));
}

#[test]
fn test_iterator_chain() {
    let data = vec![10, 5, 15, 3, 20, 8, 12];

    // Filter, map, collect into priority queue
    let pq: PriorityQueue<i32, MinHeap> = data.into_iter()
        .filter(|x| x % 2 == 0)  // Even numbers only
        .map(|x| x / 2)           // Halve them
        .collect();

    let result: Vec<i32> = pq.into_iter().collect();
    assert_eq!(result, vec![4, 5, 6, 10]);  // [8/2, 10/2, 12/2, 20/2] sorted
}

#[test]
fn test_for_loop() {
    let mut pq: PriorityQueue<i32, MinHeap> = PriorityQueue::new();
    pq.push(3);
    pq.push(1);
    pq.push(2);

    let mut result = Vec::new();
    for item in pq {
        result.push(item);
    }

    assert_eq!(result, vec![1, 2, 3]);
}

#[test]
fn test_extend() {
    let mut pq: PriorityQueue<i32, MinHeap> = PriorityQueue::new();
    pq.push(5);

    pq.extend(vec![3, 7, 1]);

    assert_eq!(pq.len(), 4);
    assert_eq!(pq.pop(), Some(1));
    assert_eq!(pq.pop(), Some(3));
    assert_eq!(pq.pop(), Some(5));
    assert_eq!(pq.pop(), Some(7));
}

#[test]
fn test_with_capacity() {
    let pq: PriorityQueue<i32, MinHeap> = PriorityQueue::with_capacity(100);

    assert_eq!(pq.len(), 0);
    assert!(pq.capacity() >= 100);
}

#[test]
fn test_reserve() {
    let mut pq: PriorityQueue<i32, MinHeap> = PriorityQueue::new();

    pq.reserve(1000);
    assert!(pq.capacity() >= 1000);

    // Add elements - should not reallocate
    for i in 0..1000 {
        pq.push(i);
    }
}

#[test]
fn test_shrink_to_fit() {
    let mut pq: PriorityQueue<i32, MinHeap> = PriorityQueue::with_capacity(1000);

    pq.push(1);
    pq.push(2);
    pq.push(3);

    assert!(pq.capacity() >= 1000);

    pq.shrink_to_fit();
    assert!(pq.capacity() < 1000);
    assert_eq!(pq.len(), 3);
}

#[test]
fn test_clear() {
    let mut pq: PriorityQueue<i32, MinHeap> = PriorityQueue::new();

    pq.push(1);
    pq.push(2);
    pq.push(3);

    pq.clear();

    assert_eq!(pq.len(), 0);
    assert!(pq.is_empty());
    assert_eq!(pq.pop(), None);
}

#[test]
fn test_size_hint() {
    let mut pq: PriorityQueue<i32, MinHeap> = PriorityQueue::new();

    pq.push(1);
    pq.push(2);
    pq.push(3);

    let mut iter = pq.into_iter();

    assert_eq!(iter.size_hint(), (3, Some(3)));
    iter.next();
    assert_eq!(iter.size_hint(), (2, Some(2)));
    iter.next();
    assert_eq!(iter.size_hint(), (1, Some(1)));
    iter.next();
    assert_eq!(iter.size_hint(), (0, Some(0)));
}

#[test]
fn test_exact_size_iterator() {
    let mut pq: PriorityQueue<i32, MinHeap> = PriorityQueue::new();

    pq.push(1);
    pq.push(2);
    pq.push(3);

    let iter = pq.into_iter();

    // ExactSizeIterator provides len()
    assert_eq!(iter.len(), 3);
}
}

What this achieves:

Now your priority queue is a first-class Rust collection:

✅ Iterator integration: Works with for loops, collect(), and iterator chains ✅ Efficient construction: FromIterator uses O(n) heapify, not O(n log n) repeated push ✅ Memory control: Pre-allocate to avoid reallocations ✅ Idiomatic Rust: Follows conventions from Vec, BinaryHeap, HashMap ✅ Zero-cost abstractions: Compiles to same code as hand-written loops

Complete Working Example

#![allow(unused)]
fn main() {
use futures::future::join_all;
use rand::Rng;
use reqwest::Client;
use std::{
    future::Future,
    sync::{Arc, Mutex},
    time::{Duration, Instant},
};
use thiserror::Error;
use tokio::{
    sync::{OwnedSemaphorePermit, Semaphore},
    time::{sleep, timeout},
};

// =============================================================================
// Milestone 1: Basic Async HTTP Client with Error Types
// =============================================================================

#[derive(Error, Debug, Clone)]
pub enum ScraperError {
    #[error("Network error: {0}")]
    NetworkError(String),

    #[error("Request timed out after {0}ms")]
    TimeoutError(u64),

    #[error("HTTP {status} error for {url}")]
    HttpError { status: u16, url: String },

    #[error("Failed to parse response: {0}")]
    ParseError(String),

    #[error("Circuit breaker is open")]
    CircuitBreakerOpen,

    #[error("Resource limit exceeded: {0}")]
    ResourceLimitExceeded(String),
}

impl From<reqwest::Error> for ScraperError {
    fn from(err: reqwest::Error) -> Self {
        if err.is_timeout() {
            return ScraperError::TimeoutError(0);
        }

        if let Some(status) = err.status() {
            return ScraperError::HttpError {
                status: status.as_u16(),
                url: err.url().map(|u| u.to_string()).unwrap_or_default(),
            };
        }

        ScraperError::NetworkError(err.to_string())
    }
}

pub async fn fetch_url(url: &str) -> Result<String, ScraperError> {
    let client = Client::new();
    let response = client.get(url).send().await.map_err(ScraperError::from)?;

    if !response.status().is_success() {
        return Err(ScraperError::HttpError {
            status: response.status().as_u16(),
            url: url.to_string(),
        });
    }

    response
        .text()
        .await
        .map_err(|e| ScraperError::ParseError(e.to_string()))
}

// =============================================================================
// Milestone 2: Enforcing Timeouts on Network Operations
// =============================================================================

pub async fn fetch_url_with_timeout(url: &str, timeout_ms: u64) -> Result<String, ScraperError> {
    match timeout(Duration::from_millis(timeout_ms), fetch_url(url)).await {
        Ok(result) => result,
        Err(_) => Err(ScraperError::TimeoutError(timeout_ms)),
    }
}

pub fn create_client(timeout_ms: u64) -> Client {
    Client::builder()
        .timeout(Duration::from_millis(timeout_ms))
        .build()
        .expect("HTTP client")
}

// =============================================================================
// Milestone 3: Retry with Exponential Backoff + Jitter
// =============================================================================

#[derive(Debug, Clone)]
pub struct RetryConfig {
    pub max_attempts: usize,
    pub initial_backoff_ms: u64,
    pub max_backoff_ms: u64,
    pub jitter: bool,
}

impl RetryConfig {
    pub fn default() -> Self {
        Self {
            max_attempts: 3,
            initial_backoff_ms: 1_000,
            max_backoff_ms: 30_000,
            jitter: true,
        }
    }

    pub fn backoff_duration(&self, attempt: usize) -> Duration {
        let multiplier = 1u64
            .checked_shl(attempt as u32)
            .unwrap_or(u64::MAX);
        let base = self.initial_backoff_ms.saturating_mul(multiplier);
        let capped = base.min(self.max_backoff_ms);
        let millis = if self.jitter {
            let mut rng = rand::thread_rng();
            (capped as f64 * rng.gen_range(0.9..1.1)) as u64
        } else {
            capped
        };
        Duration::from_millis(millis)
    }
}

impl ScraperError {
    pub fn is_retryable(&self) -> bool {
        matches!(
            self,
            ScraperError::NetworkError(_)
                | ScraperError::TimeoutError(_)
                | ScraperError::HttpError { status: 500..=599, .. }
        )
    }
}

struct RetryOutcome {
    result: Result<String, ScraperError>,
    attempt_count: usize,
}

async fn fetch_with_retry_internal(
    client: &Client,
    url: &str,
    timeout_ms: u64,
    retry_config: &RetryConfig,
) -> RetryOutcome {
    let mut attempt = 0;
    let max_attempts = retry_config.max_attempts.max(1);

    loop {
        attempt += 1;
        let future = async {
            let response = client.get(url).send().await.map_err(ScraperError::from)?;
            if !response.status().is_success() {
                return Err(ScraperError::HttpError {
                    status: response.status().as_u16(),
                    url: url.to_string(),
                });
            }

            response
                .text()
                .await
                .map_err(|e| ScraperError::ParseError(e.to_string()))
        };
        let result = match timeout(Duration::from_millis(timeout_ms), future).await {
            Ok(output) => output,
            Err(_) => Err(ScraperError::TimeoutError(timeout_ms)),
        };

        match result {
            Ok(body) => {
                return RetryOutcome {
                    result: Ok(body),
                    attempt_count: attempt,
                }
            }
            Err(err) => {
                if attempt >= max_attempts || !err.is_retryable() {
                    return RetryOutcome {
                        result: Err(err),
                        attempt_count: attempt,
                    };
                }

                let delay = retry_config.backoff_duration(attempt - 1);
                sleep(delay).await;
            }
        }
    }
}

pub async fn fetch_with_retry(
    url: &str,
    timeout_ms: u64,
    retry_config: &RetryConfig,
) -> Result<String, ScraperError> {
    let client = create_client(timeout_ms);
    fetch_with_retry_internal(&client, url, timeout_ms, retry_config)
        .await
        .result
}

// =============================================================================
// Milestone 4: Circuit Breaker Pattern
// =============================================================================

#[derive(Debug, Clone, PartialEq)]
pub enum CircuitState {
    Closed,
    Open { opened_at: Instant },
    HalfOpen,
}

pub struct CircuitBreaker {
    state: Arc<Mutex<CircuitState>>,
    failure_threshold: usize,
    success_threshold: usize,
    timeout: Duration,
    consecutive_failures: Arc<Mutex<usize>>,
    consecutive_successes: Arc<Mutex<usize>>,
}

impl CircuitBreaker {
    pub fn new(failure_threshold: usize, timeout: Duration) -> Self {
        Self {
            state: Arc::new(Mutex::new(CircuitState::Closed)),
            failure_threshold: failure_threshold.max(1),
            success_threshold: 1,
            timeout,
            consecutive_failures: Arc::new(Mutex::new(0)),
            consecutive_successes: Arc::new(Mutex::new(0)),
        }
    }

    pub fn state(&self) -> CircuitState {
        self.state.lock().unwrap().clone()
    }

    fn should_attempt(&self) -> bool {
        let mut state = self.state.lock().unwrap();
        match *state {
            CircuitState::Open { opened_at } => {
                if opened_at.elapsed() >= self.timeout {
                    *state = CircuitState::HalfOpen;
                    true
                } else {
                    false
                }
            }
            _ => true,
        }
    }

    pub async fn call<F, T>(&self, f: F) -> Result<T, ScraperError>
    where
        F: Future<Output = Result<T, ScraperError>>,
    {
        if !self.should_attempt() {
            return Err(ScraperError::CircuitBreakerOpen);
        }

        match f.await {
            Ok(value) => {
                self.on_success();
                Ok(value)
            }
            Err(err) => {
                self.on_failure();
                Err(err)
            }
        }
    }

    fn on_success(&self) {
        *self.consecutive_failures.lock().unwrap() = 0;
        let mut successes = self.consecutive_successes.lock().unwrap();
        *successes += 1;

        let mut state = self.state.lock().unwrap();
        if matches!(*state, CircuitState::HalfOpen) && *successes >= self.success_threshold {
            *state = CircuitState::Closed;
            *successes = 0;
        }
    }

    fn on_failure(&self) {
        *self.consecutive_successes.lock().unwrap() = 0;
        let mut failures = self.consecutive_failures.lock().unwrap();
        *failures += 1;

        if *failures >= self.failure_threshold {
            let mut state = self.state.lock().unwrap();
            *state = CircuitState::Open {
                opened_at: Instant::now(),
            };
            *failures = 0;
        }
    }
}

// =============================================================================
// Milestone 5: Concurrent Fetching + Partial Results
// =============================================================================

#[derive(Debug)]
pub struct FetchResult {
    pub url: String,
    pub result: Result<String, ScraperError>,
    pub duration_ms: u64,
    pub attempt_count: usize,
}

impl FetchResult {
    pub fn is_success(&self) -> bool {
        self.result.is_ok()
    }

    pub fn content(&self) -> Option<&str> {
        self.result.as_ref().ok().map(|s| s.as_str())
    }
}

#[derive(Debug)]
pub struct FetchSummary {
    pub total: usize,
    pub success: usize,
    pub failed: usize,
    pub total_duration_ms: u64,
    pub avg_duration_ms: u64,
}

impl FetchSummary {
    pub fn from_results(results: &[FetchResult]) -> Self {
        let total = results.len();
        let success = results.iter().filter(|r| r.is_success()).count();
        let failed = total.saturating_sub(success);
        let total_duration_ms: u64 = results.iter().map(|r| r.duration_ms).sum();
        let avg_duration_ms = if total > 0 {
            total_duration_ms / total as u64
        } else {
            0
        };

        Self {
            total,
            success,
            failed,
            total_duration_ms,
            avg_duration_ms,
        }
    }

    pub fn success_rate(&self) -> f64 {
        if self.total == 0 {
            0.0
        } else {
            (self.success as f64 / self.total as f64) * 100.0
        }
    }
}

pub async fn fetch_all(
    urls: Vec<String>,
    timeout_ms: u64,
    retry_config: &RetryConfig,
    circuit_breaker: &Arc<CircuitBreaker>,
) -> Vec<FetchResult> {
    let client = create_client(timeout_ms);

    let futures = urls.into_iter().map(|url| {
        let client = client.clone();
        let retry = retry_config.clone();
        let breaker = circuit_breaker.clone();

        async move {
            let start = Instant::now();
            let attempts = Arc::new(Mutex::new(0_usize));
            let attempts_inner = attempts.clone();

            let result = breaker
                .call(async {
                    let outcome = fetch_with_retry_internal(&client, &url, timeout_ms, &retry).await;
                    *attempts_inner.lock().unwrap() = outcome.attempt_count;
                    outcome.result
                })
                .await;

            let attempt_count = {
                let guard = attempts.lock().unwrap();
                *guard
            };

            FetchResult {
                url,
                result,
                duration_ms: start.elapsed().as_millis() as u64,
                attempt_count,
            }
        }
    });

    join_all(futures).await
}

pub async fn fetch_all_with_limit(
    urls: Vec<String>,
    timeout_ms: u64,
    retry_config: &RetryConfig,
    circuit_breaker: &Arc<CircuitBreaker>,
    max_concurrent: usize,
) -> Vec<FetchResult> {
    let semaphore = Arc::new(Semaphore::new(max_concurrent.max(1)));
    let client = create_client(timeout_ms);

    let futures = urls.into_iter().map(|url| {
        let semaphore = semaphore.clone();
        let client = client.clone();
        let retry = retry_config.clone();
        let breaker = circuit_breaker.clone();

        async move {
            let _permit = semaphore.acquire_owned().await.expect("permit");
            let start = Instant::now();
            let attempts = Arc::new(Mutex::new(0_usize));
            let attempts_inner = attempts.clone();

            let result = breaker
                .call(async {
                    let outcome = fetch_with_retry_internal(&client, &url, timeout_ms, &retry).await;
                    *attempts_inner.lock().unwrap() = outcome.attempt_count;
                    outcome.result
                })
                .await;

            let attempt_count = {
                let guard = attempts.lock().unwrap();
                *guard
            };

            FetchResult {
                url,
                result,
                duration_ms: start.elapsed().as_millis() as u64,
                attempt_count,
            }
        }
    });

    join_all(futures).await
}

// =============================================================================
// Milestone 6: Rate Limiting and Resource Management
// =============================================================================

#[derive(Clone)]
pub struct RateLimiter {
    semaphore: Arc<Semaphore>,
    rate_per_second: f64,
    last_request: Arc<Mutex<Instant>>,
}

impl RateLimiter {
    pub fn new(max_concurrent: usize, rate_per_second: f64) -> Self {
        Self {
            semaphore: Arc::new(Semaphore::new(max_concurrent.max(1))),
            rate_per_second: rate_per_second.max(0.1),
            last_request: Arc::new(Mutex::new(Instant::now() - Duration::from_secs(1))),
        }
    }

    pub async fn acquire(&self) -> OwnedSemaphorePermit {
        let permit = self.semaphore.clone().acquire_owned().await.expect("permit");
        let interval = Duration::from_secs_f64(1.0 / self.rate_per_second);
        let mut last = self.last_request.lock().unwrap();
        let now = Instant::now();
        let next_allowed = *last + interval;
        if now < next_allowed {
            sleep(next_allowed - now).await;
        }
        *last = Instant::now();
        permit
    }
}

pub struct ResourceManager {
    active_requests: Arc<Mutex<usize>>,
    total_bytes: Arc<Mutex<u64>>,
    max_memory_bytes: u64,
}

impl ResourceManager {
    pub fn new(max_memory_bytes: u64) -> Self {
        Self {
            active_requests: Arc::new(Mutex::new(0)),
            total_bytes: Arc::new(Mutex::new(0)),
            max_memory_bytes,
        }
    }

    pub fn can_proceed(&self) -> bool {
        *self.total_bytes.lock().unwrap() <= self.max_memory_bytes
    }

    pub fn start_request(&self) {
        *self.active_requests.lock().unwrap() += 1;
    }

    pub fn end_request(&self, bytes: u64) {
        let mut active = self.active_requests.lock().unwrap();
        if *active > 0 {
            *active -= 1;
        }
        *self.total_bytes.lock().unwrap() += bytes;
    }
}

pub async fn fetch_all_managed(
    urls: Vec<String>,
    timeout_ms: u64,
    retry_config: &RetryConfig,
    circuit_breaker: &Arc<CircuitBreaker>,
    rate_limiter: &RateLimiter,
    resource_manager: &Arc<ResourceManager>,
) -> Vec<FetchResult> {
    let client = create_client(timeout_ms);

    let futures = urls.into_iter().map(|url| {
        let client = client.clone();
        let retry = retry_config.clone();
        let breaker = circuit_breaker.clone();
        let limiter = rate_limiter.clone();
        let manager = resource_manager.clone();

        async move {
            let permit = limiter.acquire().await;
            if !manager.can_proceed() {
                drop(permit);
                return FetchResult {
                    url,
                    result: Err(ScraperError::ResourceLimitExceeded(
                        "memory limit reached".to_string(),
                    )),
                    duration_ms: 0,
                    attempt_count: 0,
                };
            }

            manager.start_request();
            let start = Instant::now();
            let attempts = Arc::new(Mutex::new(0_usize));
            let attempts_inner = attempts.clone();

            let result = breaker
                .call(async {
                    let outcome = fetch_with_retry_internal(&client, &url, timeout_ms, &retry).await;
                    *attempts_inner.lock().unwrap() = outcome.attempt_count;
                    outcome.result
                })
                .await;

            let attempt_count = {
                let guard = attempts.lock().unwrap();
                *guard
            };

            let bytes = result.as_ref().ok().map(|body| body.len() as u64).unwrap_or(0);
            manager.end_request(bytes);
            drop(permit);

            FetchResult {
                url,
                result,
                duration_ms: start.elapsed().as_millis() as u64,
                attempt_count,
            }
        }
    });

    join_all(futures).await
}

// =============================================================================
// Tests for All Milestones
// =============================================================================

#[cfg(test)]
mod tests {
    use super::*;
    use std::sync::atomic::{AtomicUsize, Ordering};
    use tokio::time::Duration;
    use wiremock::{matchers::{method, path}, Mock, MockServer, ResponseTemplate};

    #[tokio::test]
    async fn test_fetch_url_success() {
        let server = MockServer::start().await;
        Mock::given(method("GET"))
            .and(path("/test"))
            .respond_with(ResponseTemplate::new(200).set_body_string("Hello"))
            .mount(&server)
            .await;

        let url = format!("{}/test", server.uri());
        let result = fetch_url(&url).await.unwrap();
        assert_eq!(result, "Hello");
    }

    #[tokio::test]
    async fn test_fetch_url_404() {
        let server = MockServer::start().await;
        Mock::given(method("GET"))
            .respond_with(ResponseTemplate::new(404))
            .mount(&server)
            .await;

        let err = fetch_url(&server.uri()).await.unwrap_err();
        match err {
            ScraperError::HttpError { status, .. } => assert_eq!(status, 404),
            _ => panic!("expected HTTP error"),
        }
    }

    #[tokio::test]
    async fn test_fetch_url_with_timeout_triggers() {
        let server = MockServer::start().await;
        Mock::given(method("GET"))
            .respond_with(ResponseTemplate::new(200).set_delay(Duration::from_secs(2)))
            .mount(&server)
            .await;

        let err = fetch_url_with_timeout(&server.uri(), 50).await.unwrap_err();
        match err {
            ScraperError::TimeoutError(ms) => assert_eq!(ms, 50),
            _ => panic!("expected timeout"),
        }
    }

    #[test]
    fn test_retry_config_backoff() {
        let cfg = RetryConfig {
            max_attempts: 5,
            initial_backoff_ms: 100,
            max_backoff_ms: 500,
            jitter: false,
        };
        assert_eq!(cfg.backoff_duration(0).as_millis(), 100);
        assert_eq!(cfg.backoff_duration(1).as_millis(), 200);
        assert_eq!(cfg.backoff_duration(2).as_millis(), 400);
        assert_eq!(cfg.backoff_duration(3).as_millis(), 500);
    }

    #[tokio::test]
    async fn test_fetch_with_retry_succeeds_after_failures() {
        let server = MockServer::start().await;
        let attempts = Arc::new(AtomicUsize::new(0));
        let attempts_clone = attempts.clone();

        Mock::given(method("GET"))
            .respond_with(move |_req: &wiremock::Request| {
                let count = attempts_clone.fetch_add(1, Ordering::SeqCst);
                if count < 2 {
                    ResponseTemplate::new(500)
                } else {
                    ResponseTemplate::new(200).set_body_string("ok")
                }
            })
            .mount(&server)
            .await;

        let cfg = RetryConfig {
            max_attempts: 3,
            initial_backoff_ms: 10,
            max_backoff_ms: 100,
            jitter: false,
        };

        let result = fetch_with_retry(&server.uri(), 1000, &cfg).await.unwrap();
        assert_eq!(result, "ok");
        assert_eq!(attempts.load(Ordering::SeqCst), 3);
    }

    #[tokio::test]
    async fn test_circuit_breaker_flow() {
        let breaker = Arc::new(CircuitBreaker::new(2, Duration::from_millis(100)));

        for _ in 0..2 {
            let _ = breaker
                .call(async { Err::<(), _>(ScraperError::NetworkError("fail".into())) })
                .await;
        }

        match breaker.state() {
            CircuitState::Open { .. } => {}
            _ => panic!("expected open"),
        }

        tokio::time::sleep(Duration::from_millis(120)).await;
        let res = breaker
            .call(async { Ok::<_, ScraperError>("ok") })
            .await
            .unwrap();
        assert_eq!(res, "ok");
        assert_eq!(breaker.state(), CircuitState::Closed);
    }

    #[tokio::test]
    async fn test_fetch_all_partial_results() {
        let server = MockServer::start().await;
        Mock::given(method("GET"))
            .and(path("/good"))
            .respond_with(ResponseTemplate::new(200).set_body_string("good"))
            .mount(&server)
            .await;
        Mock::given(method("GET"))
            .and(path("/bad"))
            .respond_with(ResponseTemplate::new(500))
            .mount(&server)
            .await;

        let urls = vec![
            format!("{}/good", server.uri()),
            format!("{}/bad", server.uri()),
        ];
        let cfg = RetryConfig {
            max_attempts: 1,
            ..RetryConfig::default()
        };
        let breaker = Arc::new(CircuitBreaker::new(5, Duration::from_secs(1)));

        let results = fetch_all(urls, 1_000, &cfg, &breaker).await;
        assert_eq!(results.len(), 2);
        assert!(results[0].is_success());
        assert!(!results[1].is_success());
    }

    #[tokio::test]
    async fn test_fetch_all_with_limit_respects_limit() {
        let server = MockServer::start().await;
        Mock::given(method("GET"))
            .respond_with(
                ResponseTemplate::new(200).set_delay(Duration::from_millis(100)),
            )
            .mount(&server)
            .await;

        let urls: Vec<_> = (0..6).map(|i| format!("{}/{}", server.uri(), i)).collect();
        let cfg = RetryConfig::default();
        let breaker = Arc::new(CircuitBreaker::new(10, Duration::from_secs(1)));

        let start = Instant::now();
        let _results = fetch_all_with_limit(urls, 1_000, &cfg, &breaker, 2).await;
        assert!(start.elapsed().as_millis() >= 300);
    }

    #[test]
    fn test_fetch_summary() {
        let results = vec![
            FetchResult {
                url: "a".into(),
                result: Ok("1".into()),
                duration_ms: 100,
                attempt_count: 1,
            },
            FetchResult {
                url: "b".into(),
                result: Err(ScraperError::NetworkError("fail".into())),
                duration_ms: 200,
                attempt_count: 2,
            },
        ];

        let summary = FetchSummary::from_results(&results);
        assert_eq!(summary.total, 2);
        assert_eq!(summary.success, 1);
        assert_eq!(summary.failed, 1);
        assert_eq!(summary.avg_duration_ms, 150);
        assert!((summary.success_rate() - 50.0).abs() < f64::EPSILON);
    }

    #[tokio::test]
    async fn test_rate_limiter_enforces_rate() {
        let limiter = RateLimiter::new(2, 5.0);
        let start = Instant::now();

        for _ in 0..5 {
            let _permit = limiter.acquire().await;
        }

        assert!(start.elapsed().as_millis() >= 800);
    }

    #[tokio::test]
    async fn test_resource_manager_tracks_usage() {
        let manager = Arc::new(ResourceManager::new(1_000));
        assert!(manager.can_proceed());
        manager.start_request();
        manager.end_request(500);
        assert!(manager.can_proceed());
        manager.start_request();
        manager.end_request(600);
        assert!(!manager.can_proceed());
    }

    #[tokio::test]
    async fn test_fetch_all_managed() {
        let server = MockServer::start().await;
        Mock::given(method("GET"))
            .respond_with(ResponseTemplate::new(200).set_body_string("data"))
            .mount(&server)
            .await;

        let urls: Vec<_> = (0..3).map(|i| format!("{}/{}", server.uri(), i)).collect();
        let cfg = RetryConfig::default();
        let breaker = Arc::new(CircuitBreaker::new(5, Duration::from_secs(1)));
        let limiter = RateLimiter::new(2, 10.0);
        let manager = Arc::new(ResourceManager::new(10_000));

        let results = fetch_all_managed(urls, 1_000, &cfg, &breaker, &limiter, &manager).await;
        assert_eq!(results.len(), 3);
        assert!(results.iter().all(|r| r.is_success()));
    }
}
}

Project-Wide Benefits

Abstraction layers achieved:

Milestone	Abstraction	Benefit
M1: Generics	Type-agnostic code	One implementation for all types
M2: Binary heap	O(log n) operations	9,000× faster than naive
M3: Phantom types	Compile-time dispatch	Zero-cost min/max variants
M4: Wrapper types	Custom orderings	Flexible comparison strategies
M5: Heapify	O(n) construction	16× faster bulk initialization
M6: Iterators	Ecosystem integration	Idiomatic, composable API

Measured improvements (10,000 elements):

Metric	Naive (M1)	Final (M6)
Push time	2.5s	0.5ms (5,000× faster)
Heapify time	2.5s	0.15ms (16,000× faster)
Memory overhead	+50% (sort buffer)	0% (PhantomData is 0 bytes)
Code duplication	2× for min/max	0% (phantom types)
Iterator support	Manual loops	`.collect()`, `for` loops

Zero-cost abstractions proven:

Abstraction	Runtime Cost	Evidence
Generics	0 (monomorphization)	`PriorityQueue<i32>` same speed as hand-written
Phantom types	0 bytes	`size_of::<PriorityQueue> == size_of::<Vec>`
Wrapper types	0 bytes	`size_of::<Reverse<T>> == size_of::<T>`
Iterators	0 (inlining)	`for` loop same as manual `while let`

Real-world applications:

✅ Dijkstra’s shortest path: Priority queue by distance
✅ Event-driven simulation: Priority queue by timestamp
✅ Task scheduling: Priority queue by deadline/priority
✅ Huffman encoding: Priority queue for tree construction
✅ A pathfinding*: Priority queue by f-score (g + h)
✅ Median maintenance: Two heaps (min + max)

Comparison to std library:

Feature	This Project	`std::collections::BinaryHeap`
O(log n) operations	✅	✅
O(n) heapify	✅	✅
Min/max variants	✅ (phantom types)	✅ (Reverse wrapper)
Custom ordering	✅ (wrapper types)	✅ (wrapper types)
Iterator support	✅	✅
API design	Educational	Production

Patterns Workbook

Generic Priority Queue

Problem Statement

Key Concepts Explained

1. Generic Type Parameters

2. Trait Bounds (Constraining Generic Types)

3. PhantomData and Zero-Sized Types (ZSTs)

4. Phantom Types for Compile-Time Dispatch

5. Ord and PartialOrd Traits (Comparison)

6. Newtype Pattern (Wrapper Types for Custom Ord)

7. Binary Heap Data Structure (Array-Based Tree)

8. Heapify Algorithm (O(n) Heap Construction)

9. FromIterator and IntoIterator Traits

10. Zero-Cost Abstractions

Connection to This Project

Milestone 1: Basic Generic Structure with Vec Backend

Milestone 2: Implement Binary Heap Structure (Sift Operations)

Milestone 3: Add Phantom Types for Min/Max Heap Variants

Milestone 4: Support Custom Orderings with Wrapper Types

Milestone 5: Implement Efficient Heapify (O(n) from Vec)

Milestone 6: Add Iterator Support and Memory Optimizations

Build The Project

Milestone 1: Basic Generic Structure with Vec Backend

Milestone 2: Implement Binary Heap Structure (Sift Operations)

Milestone 3: Add Phantom Types for Min/Max Heap Variants

Milestone 4: Support Custom Orderings with Wrapper Types

Milestone 5: Implement Efficient Heapify (O(n) from Vec)

Milestone 6: Add Iterator Support and Memory Optimizations

Complete Working Example

Project-Wide Benefits

Keyboard shortcuts

Patterns Workbook