Struct FibonacciHeap

pub struct FibonacciHeap<T> { /* private fields */ }

A priority queue implementation backed by a Fibonacci heap.

FibonacciHeap::pop removes the smallest item.

TODO: implement change_value.

Example

use rust_dsa::FibonacciHeap;

// First, we create a new heap.
let mut heap = FibonacciHeap::new();

// Then we can add items in any order.
heap.insert(4);
heap.insert(1);
heap.insert(3);

// We can peek at the minimum item.
assert_eq!(heap.peek(), Some(&1));

// And pop them off in ascending order.
assert_eq!(heap.pop(), Some(1));
assert_eq!(heap.pop(), Some(3));
assert_eq!(heap.pop(), Some(4));
assert_eq!(heap.pop(), None);

// We can also create heaps from arrays.
let mut heap = FibonacciHeap::from([2, 6, 2]);

// And heaps can contain duplicate items.
assert_eq!(heap.pop(), Some(2));
assert_eq!(heap.pop(), Some(2));

assert_eq!(heap.len(), 1);

// We can also join two heaps together.
let mut heap: FibonacciHeap<_> = "xbz".chars().collect();
let other: FibonacciHeap<_> = "ayc".chars().collect();
heap.extend(other);

assert_eq!(heap.len(), 6);
assert_eq!(heap.pop(), Some('a'));
assert_eq!(heap.pop(), Some('b'));
assert_eq!(heap.pop(), Some('c'));
assert_eq!(heap.pop(), Some('x'));
assert_eq!(heap.pop(), Some('y'));
assert_eq!(heap.pop(), Some('z'));
assert_eq!(heap.pop(), None);

Runtime complexity

Operation	Runtime Complexity
FibonacciHeap::insert	O(1)
FibonacciHeap::peek	O(1)
FibonacciHeap::pop	O(log n)
FibonacciHeap::extend	O(1)
FibonacciHeap::from	unclear…

Implementations

impl<T> FibonacciHeap<T>

pub fn new() -> FibonacciHeap<T>

Creates a new heap.

pub fn insert(&mut self, value: T)

where T: Ord,

Inserts a value into the heap.

Example

use rust_dsa::FibonacciHeap;

let mut heap = FibonacciHeap::new();
heap.insert(4);
heap.insert(1);
heap.insert(3);

assert_eq!(heap.len(), 3);
assert_eq!(heap.peek(), Some(&1));

pub fn peek(&self) -> Option<&T>

Returns the smallest item in the heap, or None if the heap is empty.

Example

use rust_dsa::FibonacciHeap;

let mut heap = FibonacciHeap::from([2, 1]);
assert_eq!(heap.peek(), Some(&1));

heap.clear();
assert_eq!(heap.peek(), None);

pub fn pop(&mut self) -> Option<T>

where T: Ord,

Removes and returns the smallest item in the heap, or returns None if the heap is empty.

Example

use rust_dsa::FibonacciHeap;

let mut heap = FibonacciHeap::from([4, 1, 3]);

assert_eq!(heap.pop(), Some(1));
assert_eq!(heap.pop(), Some(3));
assert_eq!(heap.pop(), Some(4));
assert_eq!(heap.pop(), None);

pub fn extend(&mut self, other: FibonacciHeap<T>)

where T: Ord,

Inserts the elements from annother heap into this one.

Example

use rust_dsa::FibonacciHeap;

let mut heap = FibonacciHeap::from([3, 4, 5]);
let other = FibonacciHeap::from([1, 2]);

heap.extend(other);

assert_eq!(heap.len(), 5);

assert_eq!(heap.pop(), Some(1));
assert_eq!(heap.pop(), Some(2));
assert_eq!(heap.pop(), Some(3));
assert_eq!(heap.pop(), Some(4));
assert_eq!(heap.pop(), Some(5));
assert_eq!(heap.pop(), None);

pub fn len(&self) -> usize

Returns the number of elements in the heap.

Example

use rust_dsa::FibonacciHeap;

let mut heap = FibonacciHeap::from([1, 2, 3]);
assert_eq!(heap.len(), 3);

heap.clear();
assert_eq!(heap.len(), 0);

pub fn is_empty(&self) -> bool

Returns true if the heap is empty.

Example

use rust_dsa::FibonacciHeap;

let mut heap = FibonacciHeap::from([1, 2]);
assert!(!heap.is_empty());

heap.clear();
assert!(heap.is_empty());

pub fn clear(&mut self)

Clears the heap.

Example

use rust_dsa::FibonacciHeap;

let mut heap = FibonacciHeap::from([1, 2]);

heap.clear();
assert!(heap.is_empty());

pub fn consolidate(&mut self)

where T: Ord,

Consolidates the heap so no two nodes have the same rank.

Trait Implementations

impl<T> Default for FibonacciHeap<T>

fn default() -> FibonacciHeap<T>

Returns the “default value” for a type.

impl<T, const N: usize> From<[T; N]> for FibonacciHeap<T>

where T: Ord,

fn from(array: [T; N]) -> FibonacciHeap<T>

where T: Ord,

Converts to this type from the input type.

impl<T> FromIterator<T> for FibonacciHeap<T>

where T: Ord,

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> FibonacciHeap<T>

Creates a heap from an iterator.

use rust_dsa::FibonacciHeap;

let mut heap: FibonacciHeap<i64> = (0..10_001).map(|_| rand::random()).collect();

let mut prev = heap.pop().unwrap();

for _ in 0..10_000 {
    assert!(&prev <= heap.peek().unwrap());
    prev = heap.pop().unwrap();
}

assert_eq!(heap.pop(), None);

impl<T> IntoIterator for FibonacciHeap<T>

where T: Ord,

fn into_iter(self) -> IntoIter<T>

Creates an iterator that iterates over the heap’s items in ascending order.

Example

use rust_dsa::FibonacciHeap;

let heap = FibonacciHeap::from([4, 2, 3, 1]);

for x in heap {
    // prints 1, 2, 3, 4
    println!("{x}");
}

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

type Item = T

The type of the elements being iterated over.