Generic Max-Heap Implementation in Rust

This project provides a generic max-heap implementation that can work with any type that implements the Ord trait for comparison.

Features

MaxHeap Struct

A complete max-heap implementation with the following operations:

• new() - Create an empty heap
• from_vec(vec) - Create a heap from an existing vector
• push(item) - Insert an element (O(log n))
• pop() - Remove and return the maximum element (O(log n))
• peek() - View the maximum element without removing it (O(1))
• len() - Get the number of elements
• is_empty() - Check if the heap is empty
• into_sorted_vec() - Convert to a sorted vector (heap sort)

Legacy Functions

For backward compatibility and direct array manipulation:

• heapify(arr) - Build a max-heap from an unsorted array
• heapify_up(arr, index) - Restore heap property upward
• heapify_down(arr, index) - Restore heap property downward

Generic Type Support

The implementation works with any type T where T: Ord + Clone. This includes:

Built-in Types

• Integers: i32, u32, i64, etc.
• Floating point: f32, f64 (be careful with NaN values)
• Strings: String, &str
• Characters: char

Custom Types

You can use custom structs and enums by implementing the required traits:

#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct Person {
    age: u32,
    name: String,
}

Custom Comparison Logic

For more complex ordering, implement Ord manually:

#[derive(Debug, Clone, PartialEq, Eq)]
struct Task {
    priority: u32,
    deadline: u32,
    name: String,
}

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

impl Ord for Task {
    fn cmp(&self, other: &Self) -> Ordering {
        // Higher priority first, then earlier deadline
        match self.priority.cmp(&other.priority) {
            Ordering::Equal => other.deadline.cmp(&self.deadline),
            other => other,
        }
    }
}

Examples

Basic Usage with Integers

use heapsort::MaxHeap;

let mut heap = MaxHeap::new();
heap.push(5);
heap.push(3);
heap.push(8);
heap.push(1);

while let Some(max) = heap.pop() {
    println!("{}", max); // Prints: 8, 5, 3, 1
}

String Sorting

let words = vec!["apple", "zebra", "banana"];
let mut heap = MaxHeap::from_vec(words.into_iter().map(String::from).collect());

// Extract in reverse alphabetical order
while let Some(word) = heap.pop() {
    println!("{}", word); // Prints: zebra, banana, apple
}

Heap Sort

let mut arr = vec![64, 34, 25, 12, 22, 11, 90];
heapify(&mut arr);  // Build max-heap

// Extract elements in sorted order
for i in (1..arr.len()).rev() {
    arr.swap(0, i);  // Move max to end
    heapify_down(&mut arr[..i], 0);  // Restore heap property
}
// arr is now sorted: [11, 12, 22, 25, 34, 64, 90]

Implementation Details

Heap Property

The max-heap property ensures that for any node at index i:

• arr[i] >= arr[2*i + 1] (left child)
• arr[i] >= arr[2*i + 2] (right child)

Index Mapping

• Parent of node at index i: (i - 1) / 2
• Left child of node at index i: 2 * i + 1
• Right child of node at index i: 2 * i + 2

Time Complexity

• Insert (push): O(log n)
• Extract max (pop): O(log n)
• Peek: O(1)
• Build heap (heapify): O(n)
• Heap sort: O(n log n)

Space Complexity

• O(n) for storing the elements
• O(log n) recursion depth (or O(1) with iterative implementation)

Running the Examples

# Run the main demo
cargo run

# Run the custom comparison example
cargo run --example custom_comparison

Why Use This Implementation?

1. Generic: Works with any comparable type
2. Flexible: Supports custom comparison logic
3. Complete: Full heap operations plus heap sort
4. Educational: Clear, well-documented code
5. Efficient: Standard heap algorithms with optimal complexity

This implementation is perfect for learning about heaps, priority queues, and generic programming in Rust!