Fibonacci Heap in Rust

A high-performance Fibonacci Heap implementation in Rust with generic type support. The Fibonacci Heap is a heap data structure consisting of a collection of trees that satisfies the minimum-heap property. Compared to binary heaps, it offers superior amortized time complexities for decrease-key and merge, making it particularly useful in graph algorithms like Dijkstra's and Prim's.

Features

Time Complexities

Supported Operations

• Insert — add a new element; returns an Rc<RefCell<Node<T>>> handle for later updates.
• Extract Min — remove and return the smallest element.
• Decrease Key — reduce the key of a node referenced by a previously obtained handle.
• Delete — remove an arbitrary node by handle in O(log n) amortized.
• Merge — merge two heaps in O(1) without ID conflicts.
• Peek Min — read the minimum key without removing it.
• Peek Min Node — return an Rc handle to the minimum node for use with decrease_key / delete.
• Into Sorted Vec — consume the heap and return all keys in ascending order.
• Validate Node — O(1) check whether a handle still refers to a node in the heap.
• Clear — remove all elements; all previously issued handles are invalidated.

Standard Rust Traits

• IntoIterator — consuming iterator yielding keys in ascending order with exact size_hint.
• FromIterator<T> — build a heap directly from any iterator: iter.collect::<GenericFibonacciHeap<_>>().
• Extend<T> — bulk-insert from an iterator: heap.extend(values).

Supported Types

Any type that implements PartialOrd + Clone + Debug + 'static can be used as a key. Predefined type aliases are provided for convenience:

Architecture

• Generic implementation — a single GenericFibonacciHeap<T> covers all key types.
• NodeRef trait — abstraction over node handles; provides get_key(), get_id(), and validate().
• Private key field — the key is read-only from outside the heap; mutation is only possible through decrease_key, preserving heap invariants.
• Per-node validity flag — each node carries a valid: bool that is set to false on extraction or clear(), allowing O(1) stale-handle detection without a global registry.
• Correct max_degree bound — consolidation uses ⌊log₂ n⌋ + ⌊log₂ n⌋/2 + 2 ≈ 1.5·log₂ n, matching the theoretical Fibonacci-heap degree bound and avoiding mid-loop reallocations.

Example Usage

Basic Integer Heap

use fibonacci_heap::{GenericFibonacciHeap, HeapError};

fn main() -> Result<(), HeapError> {
    let mut heap = GenericFibonacciHeap::<i32>::new();

    // insert() returns a node handle that can be used for decrease_key later
    let node_a = heap.insert(42)?;
    let node_b = heap.insert(17)?;
    let _node_c = heap.insert(8)?; // current minimum

    assert_eq!(heap.peek_min(), Some(8));

    // Decrease node_b from 17 → 3; it becomes the new minimum
    heap.decrease_key(&node_b, 3)?;
    assert_eq!(heap.peek_min(), Some(3));

    // Extract minima in ascending order
    assert_eq!(heap.extract_min(), Some(3));
    assert_eq!(heap.extract_min(), Some(8));
    assert_eq!(heap.extract_min(), Some(42));
    assert_eq!(heap.extract_min(), None); // heap is empty

    Ok(())
}

Reading a Node's Key

The key field is private to protect heap invariants. Use the NodeRef trait or the key() method on the borrowed node:

use fibonacci_heap::{GenericFibonacciHeap, NodeRef};

let mut heap = GenericFibonacciHeap::<i32>::new();
let node = heap.insert(42).unwrap();

// Via the NodeRef trait (clones the value)
let k: i32 = node.get_key();
assert_eq!(k, 42);

// Via a direct borrow (zero-copy reference)
let k_ref: &i32 = &*node.borrow(); // borrows Node<i32>, then calls key()
// or equivalently:
assert_eq!(*node.borrow().key(), 42);

Using Type Aliases

use fibonacci_heap::{FibonacciHeapI32, FibonacciHeapF64, HeapError};

fn main() -> Result<(), HeapError> {
    let mut int_heap = FibonacciHeapI32::new();
    int_heap.insert(100)?;
    int_heap.insert(50)?;
    assert_eq!(int_heap.extract_min(), Some(50));

    let mut float_heap = FibonacciHeapF64::new();
    let node = float_heap.insert(3.14)?;
    float_heap.decrease_key(&node, 2.71)?;
    assert_eq!(float_heap.extract_min(), Some(2.71));

    Ok(())
}

Merging Two Heaps

Nodes from both heaps retain correct validity after a merge — there is no ID-space collision between independently created heaps.

use fibonacci_heap::FibonacciHeapI32;

let mut heap1 = FibonacciHeapI32::new();
heap1.insert(10).unwrap();
heap1.insert(30).unwrap();

let mut heap2 = FibonacciHeapI32::new();
heap2.insert(5).unwrap();
heap2.insert(20).unwrap();

// Merge heap2 into heap1; heap2 is consumed
heap1.merge(heap2);

assert_eq!(heap1.extract_min(), Some(5));
assert_eq!(heap1.extract_min(), Some(10));
assert_eq!(heap1.extract_min(), Some(20));
assert_eq!(heap1.extract_min(), Some(30));

Error Handling

use fibonacci_heap::{FibonacciHeapI32, FibonacciHeapF64, HeapError};

fn main() -> Result<(), HeapError> {
    let mut heap = FibonacciHeapI32::new();
    let node = heap.insert(10)?;

    // Attempting to increase a key returns InvalidKey
    assert_eq!(heap.decrease_key(&node, 15), Err(HeapError::InvalidKey));

    // A handle from a different heap returns NodeNotFound
    let mut other = FibonacciHeapI32::new();
    let foreign = other.insert(99)?;
    assert_eq!(heap.decrease_key(&foreign, 5), Err(HeapError::NodeNotFound));

    // An already-extracted node also returns NodeNotFound
    heap.extract_min(); // removes key=10
    assert_eq!(heap.decrease_key(&node, 1), Err(HeapError::NodeNotFound));

    // NaN as a new key returns KeyComparisonError
    let mut fheap = FibonacciHeapF64::new();
    let fnode = fheap.insert(10.0)?;
    assert_eq!(
        fheap.decrease_key(&fnode, f64::NAN),
        Err(HeapError::KeyComparisonError)
    );

    Ok(())
}

Deleting an Arbitrary Node

use fibonacci_heap::GenericFibonacciHeap;

let mut heap = GenericFibonacciHeap::<i32>::new();
heap.insert(1).unwrap();
let mid = heap.insert(50).unwrap();
heap.insert(100).unwrap();

// Remove 50 without knowing its position in the tree
heap.delete(&mid).unwrap();
assert_eq!(heap.len(), 2);

// The handle is now invalid
assert!(!heap.validate_node(&mid));

assert_eq!(heap.extract_min(), Some(1));
assert_eq!(heap.extract_min(), Some(100));

Iterator, FromIterator, Extend

use fibonacci_heap::GenericFibonacciHeap;

// Build from an iterator
let heap: GenericFibonacciHeap<i32> = vec![5, 3, 8, 1].into_iter().collect();

// Consume as a sorted iterator
let sorted: Vec<i32> = heap.into_iter().collect();
assert_eq!(sorted, vec![1, 3, 5, 8]);

// Extend an existing heap
let mut heap2 = GenericFibonacciHeap::<i32>::new();
heap2.insert(10).unwrap();
heap2.extend([2, 7, 4]);
assert_eq!(heap2.into_sorted_vec(), vec![2, 4, 7, 10]);

Node Validity and clear()

use fibonacci_heap::GenericFibonacciHeap;

let mut heap = GenericFibonacciHeap::<i32>::new();
let handle = heap.insert(7).unwrap();

assert!(heap.validate_node(&handle)); // present in heap

heap.clear();

// After clear(), all previously issued handles are invalidated
assert!(!heap.validate_node(&handle));
assert!(heap.is_empty());

Working with Other Types

use fibonacci_heap::{FibonacciHeapChar, FibonacciHeapF64, HeapError};

fn main() -> Result<(), HeapError> {
    let mut char_heap = FibonacciHeapChar::new();
    char_heap.insert('z')?;
    char_heap.insert('a')?;
    assert_eq!(char_heap.extract_min(), Some('a'));

    let mut float_heap = FibonacciHeapF64::new();
    float_heap.insert(2.5)?;
    float_heap.insert(1.2)?;
    assert_eq!(float_heap.extract_min(), Some(1.2));

    Ok(())
}

License

This project is licensed under the MIT License — see the LICENSE file for details.