Module std::heap

BinaryHeap, a priority queue: the greatest element by Ord (see std::cmp) is read in O(1) and removed in O(log n). Pushing asks with Alloc because the buffer may grow; nothing else allocates.

Source: std/heap.weir; committed interface: std/heap.iface. Index

struct BinaryHeap

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

A max-heap over a growable buffer, as Rust's BinaryHeap.

BinaryHeap::peek is O(1); BinaryHeap::push is O(log n) comparisons and amortised O(1) allocation (the buffer doubles); BinaryHeap::pop is O(log n). Elements that compare Equal leave in no particular order. Dropping the heap destroys its elements.

impl<T> BinaryHeap<T>

method len

pub fn len(&self) -> usize

The number of elements.

Committed interface (std/heap.iface): the signature alone.

method is_empty

pub fn is_empty(&self) -> Bool

Whether the heap holds no element.

Committed interface (std/heap.iface): the signature alone.

method peek

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

The greatest element; None when empty. O(1).

Committed interface (std/heap.iface): the signature alone.

impl<T: Ord> BinaryHeap<T>

method pop

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

Removes and returns the greatest element; None when empty. O(log n).

Committed interface (std/heap.iface):

bound Ord: Ord<T> any row {Diverge}
may diverge
scheduling point: Ord not quiet
holds what may not move at a scheduling point: Ord not quiet
enters the backing of self
writes through self: {items.len} and its shape
stores T in regions _
writes regions type T
loan of Ord across the backing of self

method into_sorted_buf

pub fn into_sorted_buf(self) -> Buf<T>

The elements in ascending order, in the heap's own buffer: a heap sort in place, O(n log n) comparisons and no allocation.

Committed interface (std/heap.iface):

bound Ord: Ord<T> any row {Diverge}
may diverge
scheduling point: Ord not quiet
holds what may not move at a scheduling point: Ord not quiet
enters the backing of self
stores T in regions _
writes regions type T
loan of Ord across the backing of self

impl<T: drops {Free}> BinaryHeap<T>

method clear

pub fn clear(&mut self) with Free

Destroys every element (with Free) and keeps the buffer's memory for reuse.

Committed interface (std/heap.iface):

bound Free: Free any
writes through self: {items.len} and its shape
destroys values of T

impl<T: drops {Alloc}> BinaryHeap<T>

method new

pub fn new() -> BinaryHeap<T> with Alloc

An empty heap; its buffer is allocated on the first push.

Committed interface (std/heap.iface):

bound Alloc: Alloc any
aborts: Alloc.alloc

method with_capacity

pub fn with_capacity(n: usize) -> BinaryHeap<T> with Alloc

An empty heap that holds n elements without growing.

Committed interface (std/heap.iface):

bound Alloc: Alloc any
aborts: Alloc.alloc

impl<T: Ord + drops {Alloc}> BinaryHeap<T>

method push

pub fn push(&mut self, x: T) with Alloc

Adds x; with Alloc because a full buffer grows (amortised O(1)), then O(log n) comparisons. A failing allocation leaves the heap as it was and drops x, as std::buf::Buf::push does.

Committed interface (std/heap.iface):

bound Alloc: Alloc any
bound Ord: Ord<T> any row {Diverge}
may diverge
aborts: Alloc.alloc
scheduling point: Ord not quiet
writes through self: {items.cap, items.data, items.len} and its shape
destroys values of T
writes regions type T
loan of Ord across the backing of self
loan of Ord across the backing of x