Struct ExPriorityQueue 

pub struct ExPriorityQueue<'a, T, C: OrdContext<T>> { /* private fields */ }

A binary-heap priority queue backed by an explicit allocator.

The “top” element is always the one for which ctx.less(top, other) is true for every other element — i.e. the element that the context considers smallest. Use a min-context for a min-heap, a max-context for a max-heap.

Invariants

• ptr is a valid allocation of cap * size_of::<T>() bytes when cap > 0.
• Elements at indices 0..len are fully initialised and satisfy the heap property: for every i, ctx.less(data[i], data[2*i+1]) and ctx.less(data[i], data[2*i+2]) are false (parent ≤ children).

Lifetime

The allocator reference 'a must outlive the ExPriorityQueue.

Implementations

impl<'a, T, C: OrdContext<T>> ExPriorityQueue<'a, T, C>

pub fn new(alloc: &'a dyn Allocator, ctx: C) -> Self

Creates a new, empty priority queue.

No allocation is performed until the first element is pushed.

Examples found in repository

examples/priority_queue.rs (line 15)

fn main() {
    let alloc = SystemAllocator;
    let ctx = MinIntContext;

    let mut pq = ExPriorityQueue::new(&alloc, ctx);

    pq.push(50);
    pq.push(10);
    pq.push(30);

    let data = [5, 1, 100];
    pq.push_slice(&data);

    while let Some(top) = pq.pop() {
        println!("Pop: {}", top);
    }
}

pub fn len(&self) -> usize

Returns the number of elements in the queue.

pub fn is_empty(&self) -> bool

Returns true if the queue is empty.

pub fn capacity(&self) -> usize

Returns the current buffer capacity in elements.

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

Returns a reference to the top (smallest/largest) element, or None if the queue is empty.

The top element is always at index 0 in the heap array.

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

Pushes value onto the queue.

Panics

Panics if the backing allocator cannot grow the buffer.

Examples found in repository

examples/priority_queue.rs (line 17)

fn main() {
    let alloc = SystemAllocator;
    let ctx = MinIntContext;

    let mut pq = ExPriorityQueue::new(&alloc, ctx);

    pq.push(50);
    pq.push(10);
    pq.push(30);

    let data = [5, 1, 100];
    pq.push_slice(&data);

    while let Some(top) = pq.pop() {
        println!("Pop: {}", top);
    }
}

pub fn try_push(&mut self, value: T) -> Result<(), T>

Attempts to push value, returning Err(value) if OOM.

pub fn push_slice(&mut self, items: &[T])

where T: Copy,

Pushes all elements in items and rebuilds the heap in O(n) time.

More efficient than calling push in a loop when many elements are added at once.

Panics

Panics if the backing allocator fails during growth.

Examples found in repository

examples/priority_queue.rs (line 22)

fn main() {
    let alloc = SystemAllocator;
    let ctx = MinIntContext;

    let mut pq = ExPriorityQueue::new(&alloc, ctx);

    pq.push(50);
    pq.push(10);
    pq.push(30);

    let data = [5, 1, 100];
    pq.push_slice(&data);

    while let Some(top) = pq.pop() {
        println!("Pop: {}", top);
    }
}

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

Removes and returns the top element, or None if empty.

Swaps the root with the last element, decrements len, and sifts the new root down to restore the heap property.

Examples found in repository

examples/priority_queue.rs (line 24)

fn main() {
    let alloc = SystemAllocator;
    let ctx = MinIntContext;

    let mut pq = ExPriorityQueue::new(&alloc, ctx);

    pq.push(50);
    pq.push(10);
    pq.push(30);

    let data = [5, 1, 100];
    pq.push_slice(&data);

    while let Some(top) = pq.pop() {
        println!("Pop: {}", top);
    }
}

pub fn remove_at(&mut self, idx: usize) -> T

Removes the element at idx and returns it.

Sifts up and down to restore the heap property regardless of whether the replacement element is smaller or larger than its neighbours.

Panics

Panics if idx >= self.len.

pub fn rebuild(&mut self)

Rebuilds the heap from scratch in O(n) via bottom-up heapification.

Called automatically by push_slice; can also be called manually after bulk insertion via unsafe direct writes.

pub fn drain_sorted(&mut self, out: &mut [T])

where T: Copy,

Drains the queue in sorted order into out.

Repeatedly pops the top element and copies it into successive positions of out. After this call the queue is empty.

Panics

Panics if out.len() < self.len().

pub fn for_each<F: FnMut(&T)>(&self, f: F)

Calls f with a reference to each element in unspecified order.

Elements are visited in heap-array order (not sorted order).

Trait Implementations

impl<T, C: OrdContext<T>> Drop for ExPriorityQueue<'_, T, C>

fn drop(&mut self)

Drops all elements and releases the backing buffer.