Struct MinHeap 

pub struct MinHeap<T>
where
    T: Ord,
{ /* private fields */ }

A binary min-heap backed by a Vec.

The smallest element (by Ord) is always at the top. Every push and pop runs in O(log n); peek is O(1).

Examples

use graph_collections::MinHeap;

let mut heap = MinHeap::new();
heap.push(5u32);
heap.push(1);
heap.push(3);

assert_eq!(heap.peek(), Some(&1));
assert_eq!(heap.pop(), Some(1));
assert_eq!(heap.pop(), Some(3));
assert_eq!(heap.pop(), Some(5));
assert!(heap.is_empty());

Implementations

impl<T> MinHeap<T>

where T: Ord,

pub fn new() -> MinHeap<T>

Creates a new, empty min-heap.

Examples

use graph_collections::MinHeap;

let heap: MinHeap<u32> = MinHeap::new();
assert!(heap.is_empty());

pub fn with_capacity(capacity: usize) -> MinHeap<T>

Creates a new, empty min-heap with at least the given capacity pre-allocated, avoiding reallocations for the first capacity pushes.

Examples

use graph_collections::MinHeap;

let heap: MinHeap<u32> = MinHeap::with_capacity(64);
assert!(heap.is_empty());

impl<T> MinHeap<T>

where T: Ord,

pub fn is_empty(&self) -> bool

Returns true if the heap contains no elements.

Examples

use graph_collections::MinHeap;

let mut heap: MinHeap<u32> = MinHeap::new();
assert!(heap.is_empty());
heap.push(1);
assert!(!heap.is_empty());

pub fn len(&self) -> usize

Returns the number of elements in the heap.

Examples

use graph_collections::MinHeap;

let mut heap: MinHeap<u32> = MinHeap::new();
assert_eq!(heap.len(), 0);
heap.push(1);
heap.push(2);
assert_eq!(heap.len(), 2);

impl<T> MinHeap<T>

where T: Ord,

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

Returns a reference to the minimum element without removing it, or None if the heap is empty.

Examples

use graph_collections::MinHeap;

let mut heap: MinHeap<u32> = MinHeap::new();
assert_eq!(heap.peek(), None);
heap.push(5);
heap.push(1);
heap.push(3);
assert_eq!(heap.peek(), Some(&1)); // minimum, not removed
assert_eq!(heap.len(), 3);

impl<T> MinHeap<T>

where T: Ord,

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

Inserts value into the heap in O(log n).

After each push, peek returns the overall minimum.

Examples

use graph_collections::MinHeap;

let mut heap: MinHeap<u32> = MinHeap::new();
heap.push(3);
heap.push(1);
heap.push(2);
assert_eq!(heap.peek(), Some(&1));

impl<T> MinHeap<T>

where T: Ord,

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

Removes and returns the minimum element in O(log n), or None if the heap is empty.

Examples

use graph_collections::MinHeap;

let mut heap: MinHeap<u32> = MinHeap::new();
assert_eq!(heap.pop(), None);
heap.push(5);
heap.push(1);
heap.push(3);
assert_eq!(heap.pop(), Some(1));
assert_eq!(heap.pop(), Some(3));
assert_eq!(heap.pop(), Some(5));
assert_eq!(heap.pop(), None);

pub fn clear(&mut self)

Removes all elements from the heap.

Examples

use graph_collections::MinHeap;

let mut heap: MinHeap<u32> = (1..=5).collect();
heap.clear();
assert!(heap.is_empty());

Trait Implementations

impl<T> Clone for MinHeap<T>

where T: Clone + Ord,

fn clone(&self) -> MinHeap<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T> Debug for MinHeap<T>

where T: Debug + Ord,

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.

impl<T> Default for MinHeap<T>

where T: Ord,

fn default() -> MinHeap<T>

Returns the “default value” for a type.

impl<T> Extend<T> for MinHeap<T>

where T: Ord,

fn extend<I>(&mut self, iter: I)

where I: IntoIterator<Item = T>,

Pushes all elements produced by the iterator into the heap.

Examples

use graph_collections::MinHeap;

let mut heap: MinHeap<u32> = MinHeap::new();
heap.push(10);
heap.extend([2, 7, 1]);
assert_eq!(heap.peek(), Some(&1));
assert_eq!(heap.len(), 4);

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T> FromIterator<T> for MinHeap<T>

where T: Ord,

fn from_iter<I>(iter: I) -> MinHeap<T>

where I: IntoIterator<Item = T>,

Builds a MinHeap from any iterator.

Uses the O(n) heapify algorithm (build-heap) rather than O(n log n) successive pushes.

Examples

use graph_collections::MinHeap;

let heap: MinHeap<u32> = vec![5, 3, 1, 4, 2].into_iter().collect();
assert_eq!(heap.peek(), Some(&1));
assert_eq!(heap.len(), 5);

impl<T> IntoIterator for MinHeap<T>

where T: Ord,

fn into_iter(self) -> <MinHeap<T> as IntoIterator>::IntoIter

Consumes the heap and yields elements in ascending order.

Examples

use graph_collections::MinHeap;

let heap: MinHeap<u32> = vec![4, 2, 5, 1, 3].into_iter().collect();
let sorted: Vec<u32> = heap.into_iter().collect();
assert_eq!(sorted, [1, 2, 3, 4, 5]);

type Item = T

The type of the elements being iterated over.

type IntoIter = MinHeapIntoIter<T>

Which kind of iterator are we turning this into?

impl<T> PartialEq for MinHeap<T>

where T: PartialEq + Ord,

fn eq(&self, other: &MinHeap<T>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T> Eq for MinHeap<T>

where T: Eq + Ord,

impl<T> StructuralPartialEq for MinHeap<T>

where T: Ord,