Struct FibHeap

Source

pub struct FibHeap<K, V> { /* private fields */ }

Expand description

A Fibonacci heap, designed for efficient priority queue operations.

This heap is implemented on top of a pie_core::ElemPool, which avoids per-node allocations and provides high performance. It is a min-heap, meaning that pop will always return the element with the smallest key.

§Type Parameters

K: The key type, which determines the priority of an element. Must implement Ord.
V: The value type, which is the data stored in the heap.

Implementations§

Source §

impl<K, V> FibHeap<K, V>

Source

pub fn new() -> Self

Creates a new, empty FibHeap.

§Examples

let mut heap = FibHeap::<u32, &str>::new();
assert!(heap.is_empty());

Source

pub fn len(&self) -> usize

Returns the number of elements in the heap.

§Complexity

O(1)

Source

pub fn is_empty(&self) -> bool

Returns true if the heap contains no elements.

§Complexity

O(1)

Source

pub fn pool_capacity(&self) -> usize

Returns the number of nodes the heap can hold without reallocating its internal storage.

This is the capacity of the underlying pie_core::ElemPool.

§Complexity

O(1)

Source

pub fn clear(&mut self)

Removes all elements from the heap.

This is an O(n) operation, as it must deallocate all nodes within its internal pool.

Source §

impl<K: Ord, V> FibHeap<K, V>

Source

pub fn push(&mut self, key: K, value: V) -> FibHandle<K, V>

Pushes a new key-value pair onto the heap.

Returns a pie_core::FibHandle which can be used with decrease_key.

§Complexity

O(1) amortized time.

§Examples

let mut heap = FibHeap::new();
let handle = heap.push(10, "ten");
assert_eq!(heap.len(), 1);

§Panics

Panics if the internal ElemPool fails to allocate a new node, which typically only happens in an out-of-memory situation.

Source

pub fn try_push( &mut self, key: K, value: V, ) -> Result<FibHandle<K, V>, IndexError>

Pushes a new key-value pair onto the heap, returning an error on allocation failure instead of panicking.

This is the fallible counterpart of push.

§Complexity

O(1) amortized time.

§Errors

Returns IndexError if the internal pool cannot allocate a new node.

§Examples

let mut heap = FibHeap::new();
let handle = heap.try_push(10, "ten").unwrap();
assert_eq!(heap.peek(), Some((&10, &"ten")));

Source

pub fn peek(&self) -> Option<(&K, &V)>

Returns a reference to the element with the smallest key, without removing it.

Returns None if the heap is empty.

§Complexity

O(1) time.

§Examples

let mut heap = FibHeap::new();
heap.push(5, 'a');
heap.push(3, 'b');

assert_eq!(heap.peek(), Some((&3, &'b')));

Source

pub fn pop(&mut self) -> Option<(K, V)>

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

Returns None if the heap is empty.

§Complexity

O(log n) amortized time.

§Examples

let mut heap = FibHeap::new();
heap.push(5, 'a');
heap.push(3, 'b');

assert_eq!(heap.pop(), Some((3, 'b')));
assert_eq!(heap.pop(), Some((5, 'a')));
assert_eq!(heap.pop(), None);

Source

pub fn decrease_key( &mut self, handle: FibHandle<K, V>, new_key: K, ) -> Result<(), DecreaseKeyError>

Decreases the key of a node in the heap.

This is a key feature of Fibonacci heaps, allowing for efficient updates to priorities. The handle must be one that was returned by a previous call to push.

§Decrease only

The design is optimized for decreasing the key at the expense of the efficiency of increasing them. Therefore, use-case where keys increase are not suitable for this implementation.

§Complexity

O(1) amortized time.

§Examples

let mut heap = FibHeap::new();
heap.push(10, "high priority");
let handle = heap.push(100, "low priority");

assert_eq!(heap.peek().unwrap().0, &10);

// Decrease the key of the "low priority" item.
heap.decrease_key(handle, 5);

// It is now the minimum element.
assert_eq!(heap.peek().unwrap().0, &5);

Source

pub fn shrink_to_fit(&mut self) -> HashMap<FibHandle<K, V>, FibHandle<K, V>>

Compacts the internal pool, reducing memory usage.

This method shrinks the underlying Vec to match the number of live nodes. Because this operation moves nodes in memory, it changes their indices.

§Returns

A IndexMap mapping old handles to new handles.

CRITICAL: If you are holding any FibHandles returned by push, you must update them using this map.

let mut heap = FibHeap::new();
let handle = heap.push(10, "data");

let map = heap.shrink_to_fit();

// Safe way to update your handle:
let new_handle = map.get(&handle).copied().unwrap_or(handle);

Source

pub fn drain(&mut self) -> Drain<'_, K, V>

Creates a draining iterator that removes all elements from the heap in ascending order of their keys and yields their (key, value) pairs.

The heap will be empty after the iterator has been fully consumed.

§Note

If the iterator is dropped before it is fully consumed, it will not remove the remaining elements. The heap will be left partially drained. This is because, unlike PieList::drain, each call to next() is an O(log n) operation, and automatically clearing the remainder on drop could be an unexpectedly expensive operation.

§Complexity

Each call to next() on the iterator has the same complexity as pop(): O(log n) amortized time. Consuming the entire iterator is equivalent to sorting the elements, taking O(n log n) time.

§Example

let mut heap = FibHeap::new();
heap.push(10, "ten");
heap.push(5, "five");
heap.push(20, "twenty");

let drained_items: Vec<_> = heap.drain().collect();
assert_eq!(drained_items, vec![(5, "five"), (10, "ten"), (20, "twenty")]);
assert!(heap.is_empty());