Priority Queue (Min-Heap) - Rust Implementation

A generic, efficient Priority Queue implementation using a Binary Min-Heap data structure in Rust.

Week 4 Project - Rust Course (Module 1: Advanced Programming)

---

Table of Contents

• Overview
• Features
• Installation
• Usage
• API Documentation
• How It Works
• Performance
• Examples
• Testing
• Project Structure

---

Overview

This project implements a Priority Queue using a Binary Min-Heap - a data structure where elements are extracted in order of priority (smallest first).

What is a Priority Queue?

A Priority Queue is an abstract data type where each element has a priority. Elements are dequeued in order of priority rather than insertion order.

Real-world applications:

• GPS navigation (Dijkstra's algorithm)
• Hospital emergency room scheduling
• Email inbox (important emails first)
• Game event systems
• Operating system task scheduling

Why Binary Heap?

Binary Heap provides efficient operations:

• Push: O(log n)
• Pop: O(log n)
• Peek: O(1)
• Memory: Compact array representation (no pointers!)

---

Features

Core Functionality

• Generic implementation (PriorityQueue<T>)
• Min-Heap (smallest element has highest priority)
• O(log n) push and pop operations
• O(1) peek operation
• Type-safe with Rust's ownership system

API Methods

• new() - Create new empty priority queue
• push(item) - Add element
• pop() - Remove and return minimum element
• peek() - View minimum element without removing
• len() - Get size
• is_empty() - Check if empty

Traits Implemented

• Default - Default constructor
• Ord requirement for generic type T

---

Installation

Clone the repository

git clone https://github.com/EEFnik/04-priority-queue.git
cd priority-queue

Run tests

cargo test

Run demo examples

cargo run

---

Usage

Basic Example

use priority_queue::PriorityQueue;

fn main() {
    let mut pq = PriorityQueue::new();

    // Add elements in any order
    pq.push(5);
    pq.push(3);
    pq.push(7);
    pq.push(1);

    // Extract in sorted order (ascending)
    println!("{}", pq.pop().unwrap()); // 1
    println!("{}", pq.pop().unwrap()); // 3
    println!("{}", pq.pop().unwrap()); // 5
    println!("{}", pq.pop().unwrap()); // 7
}

With Custom Types

use std::cmp::Ordering;

#[derive(Eq, PartialEq)]
struct Task {
    name: String,
    priority: u8,  // 1 = highest, 5 = lowest
}

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

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

fn main() {
    let mut scheduler = PriorityQueue::new();

    scheduler.push(Task { name: "Email".into(), priority: 3 });
    scheduler.push(Task { name: "Bug Fix".into(), priority: 1 });
    scheduler.push(Task { name: "Coffee".into(), priority: 5 });

    // Process tasks by priority
    while let Some(task) = scheduler.pop() {
        println!("Processing: {}", task.name);
    }
    // Output:
    // Processing: Bug Fix (priority 1)
    // Processing: Email (priority 3)
    // Processing: Coffee (priority 5)
}

---

API Documentation

PriorityQueue<T: Ord>

Constructor

pub fn new() -> Self

Creates a new empty priority queue.

Example:

let pq: PriorityQueue<i32> = PriorityQueue::new();

---

push

pub fn push(&mut self, item: T)

Adds an element to the priority queue.

Time complexity: O(log n)

Example:

pq.push(42);

---

pop

pub fn pop(&mut self) -> Option<T>

Removes and returns the element with the highest priority (smallest value).

Returns: Some(T) if queue is not empty, None otherwise.

Time complexity: O(log n)

Example:

if let Some(min) = pq.pop() {
    println!("Minimum: {}", min);
}

---

peek

pub fn peek(&self) -> Option<&T>

Returns a reference to the element with highest priority without removing it.

Returns: Some(&T) if queue is not empty, None otherwise.

Time complexity: O(1)

Example:

if let Some(min) = pq.peek() {
    println!("Next: {}", min);
}

---

len

pub fn len(&self) -> usize

Returns the number of elements in the queue.

Time complexity: O(1)

---

is_empty

pub fn is_empty(&self) -> bool

Returns true if the queue is empty.

Time complexity: O(1)

---

How It Works

Binary Heap Structure

A Binary Heap is a complete binary tree stored in an array (Vec).

Tree Representation

        1
       / \
      3   5
     / \ / \
    7  8 9  10

Array Representation

[1, 3, 5, 7, 8, 9, 10]
 0  1  2  3  4  5  6   <- indices

Index Formulas

For element at index i:

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

Heap Property

Min-Heap Property: Parent ≤ Children

For every node, the value is less than or equal to its children's values.

Operations

Push (Bubble Up)

1. Add element to end of array
2. Compare with parent
3. If smaller than parent → swap
4. Repeat until heap property satisfied

Example:

Initial: [1, 3, 5, 7, 8]
Push(2):
  Step 1: [1, 3, 5, 7, 8, 2]  (add to end)
  Step 2: [1, 3, 2, 7, 8, 5]  (bubble up: 2 < 5, swap)
  Step 3: [1, 2, 5, 7, 8, 3]  (continue)
  Done: heap property restored

Pop (Bubble Down)

1. Save minimum (first element)
2. Move last element to first position
3. Compare with children
4. Swap with smallest child if needed
5. Repeat until heap property satisfied
6. Return saved minimum

---

Performance

Time Complexity

Operation	Time Complexity	Space
new()	O(1)	O(1)
push()	O(log n)	O(1) amortized
pop()	O(log n)	O(1)
peek()	O(1)	O(1)
len()	O(1)	O(1)
is_empty()	O(1)	O(1)

Why O(log n)?

Binary heap has logarithmic height:

• Height = log₂(n)
• For 1,000 elements → ~10 operations
• For 1,000,000 elements → ~20 operations

Example benchmark:

Size: 10,000 elements
  Push 10,000 elements: 2ms
  Pop  10,000 elements: 1.8ms

---

Examples

Example 1: Sorting Numbers

let mut pq = PriorityQueue::new();

for num in vec![5, 3, 7, 1, 9, 2] {
    pq.push(num);
}

while let Some(num) = pq.pop() {
    print!("{} ", num);  // Output: 1 2 3 5 7 9
}

Example 2: Strings (Lexicographic Order)

let mut pq = PriorityQueue::new();

for word in vec!["zebra", "apple", "mango", "banana"] {
    pq.push(word.to_string());
}

// Output: apple, banana, mango, zebra

Example 3: Dijkstra's Algorithm Simulation

#[derive(Eq, PartialEq)]
struct Node {
    id: usize,
    distance: usize,
}

impl Ord for Node {
    fn cmp(&self, other: &Self) -> Ordering {
        self.distance.cmp(&other.distance)
    }
}

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

let mut pq = PriorityQueue::new();

// Add nodes with distances
pq.push(Node { id: 0, distance: 0 });
pq.push(Node { id: 1, distance: 4 });
pq.push(Node { id: 2, distance: 2 });

// Process nodes in order of distance
while let Some(node) = pq.pop() {
    println!("Visit node {} (distance: {})", node.id, node.distance);
}

More examples in src/main.rs!

---

Testing

Run all tests

cargo test

Run unit tests only

cargo test --lib

Run integration tests only

cargo test --test integration_tests

Test coverage

• Unit tests: 5 tests in src/lib.rs
• Integration tests: 15 tests in tests/integration_tests.rs
• Total coverage: ~95% of functionality

Key test scenarios

• Basic operations (push, pop, peek)
• Edge cases (empty queue, single element)
• Different types (i32, String, custom structs)
• Large datasets (10,000 elements)
• Heap property maintenance
• Duplicate values
• Stress testing

---

Project Structure

priority-queue/
├── Cargo.toml              # Project metadata
├── README.md               # This file
├── src/
│   ├── lib.rs             # PriorityQueue implementation + unit tests
│   └── main.rs            # Demo examples (5 examples)
└── tests/
    └── integration_tests.rs  # Integration tests

---

Learning Outcomes

This project demonstrates understanding of:

Rust Concepts

• Generics - PriorityQueue<T: Ord>
• Traits - Ord, Default, custom trait implementations
• Lifetimes - References in peek() method
• Ownership - Move semantics, borrowing
• Error Handling - Option<T> for safe operations

Data Structures & Algorithms

• Binary Heap - Array-based tree representation
• Heap Property - Maintaining invariants
• Bubble Up/Down - Efficient rebalancing
• Time Complexity - O(log n) operations

Software Engineering

• Testing - Unit and integration tests
• Documentation - Clear API documentation
• Code Organization - Separation of concerns
• Best Practices - Idiomatic Rust code

---

Future Enhancements

Possible additions:

• Display trait for pretty printing
• IntoIterator for iterator support
• from_vec() with efficient heapify
• Max-heap variant
• Custom comparator support
• Merge operation for two heaps
• Benchmarking suite

---

Resources

Theory:

• Binary Heap (Wikipedia)
• Priority Queue Applications
• Visualize Heap Operations

Rust Concepts:

• The Rust Book - Generics
• The Rust Book - Traits
• Rust std::collections::BinaryHeap

---