Struct crater::fheap::FibHeap

pub struct FibHeap<'a, T: Node<'a> + ?Sized, U> { /* private fields */ }

A fibonacci heap is a type of data structure optimized for use as a priority queue. It is commonly useful in pathfinding algorithms like Dijkstra’s and A*. Fib heaps have the following amortized time complexities:

• find-min: O(1)
• extract-min: O(logn)
• insert: O(1), compare to O(logn) in a binary heap
• decrease-key: O(1), compare to O(logn) in a binary heap / pairing heap
• meld: O(1), compare to O(n) in a binary heap Extracting (or deleting) an arbitrary element is also O(logn). Increase-key is not directly supported, but can be done by removing and reinserting. Fib heaps will generally be a better choice than other heaps when:
• The number of elements extracted from the heap is proportional to the number inserted and/or large, not fixed and small
• The keys/priorities of elements need to be decreased frequently
• The keys/priorities of elements don’t need to be increased frequently (also the comparison function doesn’t need to be changed)

Implementations

impl<'a, T: Node<'a> + ?Sized + 'a, U> FibHeap<'a, T, U>

pub fn new(_container: &'a U) -> Self

Create a new fibonacci heap whose backing storage will live at least as long as _container. Typically, if the nodes are stored in a Vec or a crate::kdtree::KdTree or so on, this backing container will have to remain effectively pinned for as long as the fibonacci heap exists, so that references to nodes remain valid.

Conceptually, only the lifespan of _container matters: by passing it in here and holding a PhantomData reference with the same lifespan, we force the shared reference to the container to outlive the fibonacci heap and prevent any mutable references to it from existing for that time.

Internally, RawNode uses UnsafeCell so that nodes can be mutated through shared reference. Otherwise, correctly mutating nodes is excessively complicated (requires using raw pointers throughout, and requires the backing storage to have some way to get a mutable subreference that doesn’t overlap with any node so we can assume it is effectively pinned, most of the time this would be a mutable reference to an empty slice).

pub fn peek_min(&self) -> Option<&'a T>

Get the minimal element if it exists, returning a reference to it without removing it. It is safe to decrease the key of the result, but not to increase it if doing so could cause it to no longer be minimal (the key probably lives behind an UnsafeCell)

pub fn pop_min(&mut self) -> Option<&'a T>

Get and remove the minimal element if it exists, returning a reference to it. The key of the result may be freely modified

pub unsafe fn push(&mut self, ent: &'a T)

Add a node to the heap. This is unsafe because the node must not already be in the heap, nor in a different heap. It is not strictly required for all nodes to have the same backing store as long as the borrow checker confirms they outlive the heap, but most of the time all references will be to elements of the backing store.

pub unsafe fn decrease_key(&mut self, ent: &'a T)

Called immediately AFTER a node’s key is decreased, to ensure that the heap invariants are maintained. This is unsafe because the node must be an element of the heap.

pub unsafe fn remove(&mut self, node: &'a T)

Remove a node from the heap by reference. Since the heap is intrusive and does not own its nodes, nothing is returned because the caller already has a reference to the removed node. This is unsafe because the node must be an element of the heap.