Crate fibonacci_heap

Fibonacci Heap implementation in Rust

This module provides a Fibonacci Heap, a priority queue with better amortized time complexity compared to a binary heap.

Features

• Efficient insertions and merging
• Quick access to the minimum element
• Support for decrease-key operations

Example Usage

Linking Nodes (During Consolidation)

use fibonacci_heap::FibonacciHeap;

let mut heap = FibonacciHeap::new();
let n1 = heap.insert(10);
let n2 = heap.insert(20);
let n3 = heap.insert(5);

// Extract min triggers consolidation
heap.extract_min();

// Nodes 10 and 20 get linked during consolidation
assert_eq!(heap.root_list.len(), 1);

Cutting Nodes (During Decrease-Key)

use fibonacci_heap::FibonacciHeap;

let mut heap = FibonacciHeap::new();
heap.insert(30);
let node = heap.insert(40);
heap.insert(10);
heap.extract_min(); // Forces consolidation

// Decrease key triggers cut from parent
heap.decrease_key(&node, 5);

// Node 40 (now 5) is promoted to root
assert_eq!(heap.extract_min(), Some(5));

Cascading Cut (Multi-Level Cutting)

use fibonacci_heap::FibonacciHeap;

let mut heap = FibonacciHeap::new();
heap.insert(100);
let parent = heap.insert(200);
heap.insert(50);
heap.extract_min(); // Consolidate to create hierarchy

heap.decrease_key(&parent, 150);
let child = heap.insert(300);
heap.extract_min(); // Create parent-child-grandchild

// Trigger cascading cut
heap.decrease_key(&child, 10); // First cut
heap.decrease_key(&parent, 20); // Second cut triggers cascade

assert_eq!(heap.extract_min(), Some(10));
assert_eq!(heap.extract_min(), Some(20));

Full Workflow with All Operations

use fibonacci_heap::FibonacciHeap;

let mut heap = FibonacciHeap::new();
let node_30 = heap.insert(30);
heap.insert(10);
let node_20 = heap.insert(20);
assert_eq!(heap.extract_min(), Some(10));

let node_40 = heap.insert(40);
heap.insert(5);
assert_eq!(heap.extract_min(), Some(5));

// Decrease keys using stored node references
heap.decrease_key(&node_40, 2);
heap.decrease_key(&node_30, 1);

assert_eq!(heap.extract_min(), Some(1));  // From node_30
assert_eq!(heap.extract_min(), Some(2));  // From node_40
assert_eq!(heap.extract_min(), Some(20)); // Original node_20

Complexity

Operation	Amortized Complexity
Insert	O(1)
Merge	O(1)
Extract Min	O(log n)
Decrease Key	O(1)

Structs

FibonacciHeap

Represents a Fibonacci Heap data structure.

Node

Represents a node in the Fibonacci Heap.