Struct maelstrom_util::heap::Heap

pub struct Heap<DepsT: HeapDeps>(/* private fields */);

A min-heap implementation that provides some features necessary for us that are missing from std::collections::BinaryHeap:

• The values (priorities) of elements can be stored outside of the heap itself. This supports a common use case where the heap just contains IDs for a specific data structure, and the actual data structures are stored elsewhere, usually in a map of some sort.
• The heap can be notified when Individual elements’ values change, via Heap::sift_up and Heap::sift_down, both of which are O(log(n)).
• If all or most of the elements’ values change, the heap can be fixed up using Heap::rebuild. This is O(n).
• Arbitrary elements can be removed from the heap in O(log(n)) time.

This heap accomplishes this by telling the elements what their heap indices are. Those heap indices are then used in the per-element methods.

Since the values of elements are stored externally from the heap, the heap relies on the client notifying it whenever a value changes. If the client doesn’t do this, the heap condition will be violated and Heap::peek will no longer necessarily provide the smallest element.

The modifying methods of this struct take a &mut HeapDeps, instead of a Heap constructor taking the dependencies and storing them in the heap. This is done to satisfy the borrow checker so that clients of the heap don’t need to use a bunch of std::rc::Rc<Refcell<_>>s.

Implementations

impl<DepsT: HeapDeps> Heap<DepsT>

pub fn peek(&self) -> Option<&DepsT::Element>

Return an Option containing an element with the smallest value in the heap, or None if the heap is empty. Note that multiple elements in the heap may have the smallest value. In this case, an arbitrary element will be returned. O(1).

pub fn pop(&mut self, deps: &mut DepsT) -> Option<DepsT::Element>

Remove the element with the smallest value in the heap, or None if the heap is empty. Note that multiple elements in the heap may have the smallest value. In this case, an arbitrary element will be returned. O(log(n)).

pub fn push(&mut self, deps: &mut DepsT, elem: DepsT::Element)

Add a new element to the heap. O(log(n)).

pub fn remove(&mut self, deps: &mut DepsT, idx: HeapIndex)

Remove the element at the given index from the heap. If the index is out of range, the function will panic. O(log(n)).

pub fn sift_up(&mut self, deps: &mut DepsT, idx: HeapIndex)

Notify the heap an element’s value has decreased. The heap will see if the element needs to be sifted up the heap. If the index is out of range, the function will panic. O(log(n)).

pub fn sift_down(&mut self, deps: &mut DepsT, idx: HeapIndex)

Notify the heap an element’s value has increased. The heap will see if the element needs to be sifted down the heap. If the index is out of range, the function will panic. O(log(n)).

pub fn rebuild(&mut self, deps: &mut DepsT)

Assume all elements’ values have changed and rebuild the heap accordingly. If one is changing the values of most of the elements in the heap, this method is faster than calling Heap::sift_up or Heap::sift_down on each element. O(n).

Trait Implementations

impl<DepsT: HeapDeps> Default for Heap<DepsT>

fn default() -> Self

Returns the “default value” for a type.