Struct BinaryHeap

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

A priority queue implementation backed by a binary heap.

BinaryHeap::pop removes the smallest item.

Example

use rust_dsa::BinaryHeap;

// First, we create a new heap.
let mut heap = BinaryHeap::new();

// Then we can add items in any order.
heap.insert(4);
heap.insert(1);
heap.insert(3);

// We can peek at the minimum item.
assert_eq!(heap.peek(), Some(&1));

// And pop them off in ascending order.
assert_eq!(heap.pop(), Some(1));
assert_eq!(heap.pop(), Some(3));
assert_eq!(heap.pop(), Some(4));
assert_eq!(heap.pop(), None);

// We can also create heaps from arrays.
let mut heap = BinaryHeap::from([2, 6, 2]);

// And heaps can contain duplicate items.
assert_eq!(heap.pop(), Some(2));
assert_eq!(heap.pop(), Some(2));

assert_eq!(heap.len(), 1);

Runtime complexity

Operation	Runtime Complexity
BinaryHeap::insert	O(log n)
BinaryHeap::peek	O(1)
BinaryHeap::pop	O(log n)
BinaryHeap::from	O(n)

Implementations

impl<T> BinaryHeap<T>

pub fn new() -> Self

Creates an empty binary heap.

pub fn insert(&mut self, item: T)

where T: Ord,

Inserts an item into the binary heap.

Example

use rust_dsa::BinaryHeap;

let mut heap = BinaryHeap::new();
heap.insert(4);
heap.insert(1);
heap.insert(3);

assert_eq!(heap.len(), 3);
assert_eq!(heap.peek(), Some(&1));

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

Returns the smallest item in the binary heap, or None if the heap is empty.

Example

use rust_dsa::BinaryHeap;

let mut heap = BinaryHeap::from([2, 1]);
assert_eq!(heap.peek(), Some(&1));

heap.clear();
assert_eq!(heap.peek(), None);

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

where T: Ord,

Removes and returns the smallest item in the binary heap, or returns None if the heap is empty.

Example

use rust_dsa::BinaryHeap;

let mut heap = BinaryHeap::from([4, 1, 3]);

assert_eq!(heap.pop(), Some(1));
assert_eq!(heap.pop(), Some(3));
assert_eq!(heap.pop(), Some(4));
assert_eq!(heap.pop(), None);

pub fn len(&self) -> usize

Returns the length of the binary heap.

Example

use rust_dsa::BinaryHeap;

let mut heap = BinaryHeap::from([1, 2, 3]);
assert_eq!(heap.len(), 3);

heap.clear();
assert_eq!(heap.len(), 0);

pub fn is_empty(&self) -> bool

Returns true if the binary heap is empty.

Example

use rust_dsa::BinaryHeap;

let mut heap = BinaryHeap::from([1, 2]);
assert!(!heap.is_empty());

heap.clear();
assert!(heap.is_empty());

pub fn clear(&mut self)

Clears the binary heap.

Example

use rust_dsa::BinaryHeap;

let mut heap = BinaryHeap::from([1, 2]);

heap.clear();
assert!(heap.is_empty());

Trait Implementations

impl<T: Clone> Clone for BinaryHeap<T>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T> Default for BinaryHeap<T>

fn default() -> BinaryHeap<T>

Returns the “default value” for a type.

impl<T, const N: usize> From<[T; N]> for BinaryHeap<T>

where T: Ord,

fn from(array: [T; N]) -> BinaryHeap<T>

where T: Ord,

Uses the heapify algorithm to create a BinaryHeap in O(n) time.

impl<T> FromIterator<T> for BinaryHeap<T>

where T: Ord,

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> BinaryHeap<T>

Uses the heapify algorithm to create a BinaryHeap in O(n) time.

impl<T> IntoIterator for BinaryHeap<T>

where T: Ord,

fn into_iter(self) -> IntoIter<T>

Creates an iterator that iterates over the heap’s items in ascending order.

Example

use rust_dsa::BinaryHeap;

let heap = BinaryHeap::from([4, 2, 3, 1]);

for x in heap {
    // prints 1, 2, 3, 4
    println!("{x}");
}

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

type Item = T

The type of the elements being iterated over.