d-ary Heap Priority Queue (Rust) v2.5.0

Wikipedia-standard d-ary heap implementation with O(1) item lookup and configurable arity.

Key Features

• d-ary heap (not binary): Configurable arity d (number of children per node)
• Min/Max flexibility: Supports both min-heap and max-heap behavior via comparators
• O(1) item lookup: Internal hash map enables efficient priority updates
• Efficient operations:
  • O(1): front(), peek(), len(), is_empty(), contains(), get_position()
  • O(log_d n): insert(), increase_priority()
  • O(d × log_d n): pop(), decrease_priority()
  • O(n): insert_many() (Floyd's heapify), to_array()
• Cross-language API: Unified methods matching C++, Go, Zig, and TypeScript implementations
• Rust-idiomatic: Uses Result<T, Error> and Option<T> return types

Installation

Add to your Cargo.toml:

[dependencies]
d-ary-heap = "2.5.0"

Quick Start

use d_ary_heap::{PriorityQueue, MinBy, MaxBy, Error};

#[derive(Clone, Eq, PartialEq, Hash)]
struct Task {
    id: u32,
    priority: u32,
}

fn main() -> Result<(), Error> {
    // Min-heap by priority (lower value = higher priority)
    let mut heap = PriorityQueue::new(4, MinBy(|t: &Task| t.priority))?;

    // Insert items
    heap.insert(Task { id: 1, priority: 10 });
    heap.insert(Task { id: 2, priority: 5 });

    // Get highest priority item
    assert_eq!(heap.front().priority, 5);

    // Update priority (make more important)
    heap.increase_priority(&Task { id: 1, priority: 1 })?;
    assert_eq!(heap.front().priority, 1);

    // Remove items in priority order
    while let Some(task) = heap.pop() {
        println!("Processing task {} with priority {}", task.id, task.priority);
    }

    Ok(())
}

Usage Examples

Basic Operations

use d_ary_heap::{PriorityQueue, MinBy};

let mut heap = PriorityQueue::new(3, MinBy(|x: &i32| *x)).unwrap();

// Insert items
heap.insert(10);
heap.insert(5);
heap.insert(15);

// Check properties
assert_eq!(heap.len(), 3);
assert!(!heap.is_empty());
assert_eq!(heap.d(), 3);

// Access highest priority (front panics if empty, peek returns Option)
assert_eq!(heap.front(), &5);
assert_eq!(heap.peek(), Some(&5));

// Remove items
assert_eq!(heap.pop(), Some(5));
assert_eq!(heap.pop(), Some(10));
assert_eq!(heap.pop(), Some(15));
assert_eq!(heap.pop(), None);

Max-Heap Example

use d_ary_heap::{PriorityQueue, MaxBy};

let mut heap = PriorityQueue::new(2, MaxBy(|x: &i32| *x)).unwrap();

heap.insert(10);
heap.insert(5);
heap.insert(15);

// Max-heap: highest value has highest priority
assert_eq!(heap.front(), &15);

Bulk Operations

use d_ary_heap::{PriorityQueue, MinBy};

let mut heap = PriorityQueue::new(3, MinBy(|x: &i32| *x)).unwrap();

// Insert many items at once (O(n) via Floyd's heapify)
heap.insert_many(vec![5, 3, 7, 1, 9]);
assert_eq!(heap.front(), &1);

// Pop multiple items at once
let items = heap.pop_many(3);
assert_eq!(items, vec![1, 3, 5]);

// Get heap contents as array
let remaining = heap.to_array();
assert_eq!(remaining.len(), 2);

Priority Updates

use d_ary_heap::{PriorityQueue, MinBy, Error};
use std::hash::{Hash, Hasher};

#[derive(Clone, Debug)]
struct Item { id: u32, cost: u32 }

// Important: Hash/Eq must be based on identity (id), not priority (cost)
impl PartialEq for Item { fn eq(&self, other: &Self) -> bool { self.id == other.id } }
impl Eq for Item {}
impl Hash for Item { fn hash<H: Hasher>(&self, state: &mut H) { self.id.hash(state) } }

let mut heap = PriorityQueue::new(3, MinBy(|x: &Item| x.cost)).unwrap();
heap.insert(Item { id: 1, cost: 10 });
heap.insert(Item { id: 2, cost: 5 });

// Increase priority (for min-heap: lower cost = higher priority)
heap.increase_priority(&Item { id: 1, cost: 1 }).unwrap();
assert_eq!(heap.front().id, 1);

// Decrease priority (for min-heap: higher cost = lower priority)
heap.decrease_priority(&Item { id: 1, cost: 20 }).unwrap();
assert_eq!(heap.front().id, 2);

// Update priority when direction is unknown
heap.update_priority(&Item { id: 2, cost: 3 }).unwrap();

// Check item position (O(1) lookup)
assert!(heap.get_position(&Item { id: 1, cost: 0 }).is_some());

Error Handling

use d_ary_heap::{PriorityQueue, MinBy, Error};

// Invalid arity returns error
let result = PriorityQueue::new(0, MinBy(|x: &i32| *x));
assert_eq!(result, Err(Error::InvalidArity));

let mut heap = PriorityQueue::new(2, MinBy(|x: &i32| *x)).unwrap();
heap.insert(5);

// Item not found error
assert_eq!(heap.increase_priority(&99), Err(Error::ItemNotFound));

// Index out of bounds error
assert_eq!(heap.increase_priority_by_index(99), Err(Error::IndexOutOfBounds));

// Clear with invalid arity
assert_eq!(heap.clear(Some(0)), Err(Error::InvalidArity));

API Reference

Core Types

Error Variants

Methods

Traits

Performance Considerations

Choosing Optimal Arity (d)

Recommendation: Start with d=4 for most workloads.

Optimization Tips

1. Use bulk insert: insert_many() is O(n) vs O(n log n) for individual inserts
2. Choose d wisely: Benchmark with your workload (d=4 often optimal)
3. Use simple comparators: Inline closures are faster than complex functions
4. Stable identity: Ensure Hash/Eq are based on stable identity, not priority

Cross-Language Compatibility

This implementation provides API parity with:

• C++: PriorityQueue<T> in Cpp/PriorityQueue.h
• Go: PriorityQueue[T] in Go/src/dheap.go
• Zig: DHeap(T) in zig/src/d_heap.zig
• TypeScript: PriorityQueue<T> in TypeScript/src/PriorityQueue.ts

All implementations share:

• Identical time complexities
• Unified method names (with language-appropriate casing)
• Cross-language API consistency

What is a d-ary Heap?

A d-ary heap is a tree structure where:

• Each node has up to d children (configurable arity)
• The root contains the highest-priority item
• Children are unordered (unlike binary heaps)
• Heap property: Each parent has higher priority than all children
• Complete tree: Filled left-to-right, level by level

Advantages over Binary Heaps (d=2)

• Shallower tree: Height is log_d(n) instead of log₂(n)
• Faster inserts: O(log_d n) vs O(log₂ n)
• Configurable: Optimize for your specific workload

Trade-offs

• Slower pops: O(d·log_d n) vs O(log₂ n)
• More comparisons: Each pop examines up to d children
• Memory: Slightly higher overhead for position tracking

Reference Implementation

This implementation follows the d-ary heap specification from:

• Wikipedia: D-ary heap
• Network Flows textbook: Section A.3, pp. 773–778
  • Ravindra Ahuja, Thomas Magnanti & James Orlin
  • Prentice Hall (1993)
  • Book information

Testing

# Run all tests
cargo test

# Run specific test
cargo test test_min_heap_ordering

# Run demo
cargo run

License

Apache License 2.0 - See LICENSE for details.