Struct bheap::BinaryMaxHeap

pub struct BinaryMaxHeap<T> where
    T: Ord + Uid,  {
    buffer: Vec<T>,
    index: HashMap<u64, usize>,
}

A re-prioritizable binary max heap containing a buffer for storing elements and a hashmap index for keeping track of element positions.

Fields

buffer: Vec<T>

in-memory storage for elements

index: HashMap<u64, usize>

mapping from element uids to positions in the heap buffer

Implementations

impl<T> BinaryMaxHeap<T> where
    T: Ord + Uid, 

pub fn from_vec(buffer: Vec<T>) -> Self

Creates a new BinaryMaxHeap from a given vector, which may or may not be empty. If the vector already contains elements, the elements are re-arranged with a build_heap() operation.

pub fn new() -> Self

Creates an empty binary max heap with no elements.

pub fn is_empty(&self) -> bool

pub fn len(&self) -> usize

pub(crate) fn swap_elems_at_indices(&mut self, i: usize, j: usize)

Swaps elements at the given indices byt first swapping the elements in the buffer vector and next updating the HashMap index with new indices.

pub(crate) fn cmp(&self, i: usize, j: usize) -> Ordering

Convenience method for comparing elements at the given indices.

pub(crate) fn heapify_up(&mut self, idx: usize) -> Option<usize>

Restores heap property by moving the element in the given index upwards along it’s parents to the root, until it has no parents or it is <= to its parents. It operates in the following manner:

heapify_up(heap, i) {
    while i > 0 {
        let parent = (i - 1) / 2;
        if heap[i] > heap[parent] {
            swap(heap, i, parent)
        } else { break; }
    }
}

pub(crate) fn heapify_dn(&mut self, idx: usize) -> Option<usize>

Restores heap property by moving the element at the given index, downwards along it’s children, towards the leaves, until it has no children or it is >= to its children. It operates in the following manner:

heapify_dn(heap, i) {
    while i < len(heap) / 2 {
        let max = i;
        let lc, rc = 2 * i + 1, 2 * i + 2;

        if lc < len(heap) && heap[max] < lc { max = lc; }
        if rc < len(heap) && heap[max] < rc { max = rc; }

        if i != max { swap(heap, i, max); i = max; }
        else { break; }
    }
}

pub(crate) fn update_index(&mut self, i: usize) -> Option<usize>

Corrects the HashMap index for the given heap position, by updating the entry with the uid of the element at that position. The values stored is the index. Concisely:

index[buffer[i].uid()] = i

pub fn get(&mut self, i: usize) -> Option<&mut T>

Returns a mutable reference to the element at the givven heap position, if present. This implementation assumes that no mutation used with respect to the returned mutable reference, modifies the uid() property for the element.

pub fn push(&mut self, elem: T)

Pushes a new element in this priority queue.

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

Peeks at the element with highest priority, if present.

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

Pops the element with the highest property, if present.

pub fn build_index(&mut self)

Builds the HashMap index from uids to buffer positions.

pub fn build_heap(&mut self)

Builds a heap from un-organized elements in the in-memory buffer. It operates as follows:

build_heap(heap) {
    build_index(heap);

    for i = len(heap) / 2; i >= 0; i-- {
        heapify_dn(heap, i);
    }
}

pub fn restore_heap_property(&mut self, idx: usize) -> Option<usize>

Restores heap property at the given position.

pub fn index_in_heap_from_uid(&self, uid: u64) -> Option<usize>

Returns the position for element with given uid in the heap buffer.

pub fn index_in_heap(&self, elem: &T) -> Option<usize>

Returns the position for element in the heap buffer.