Struct std::collections::BinaryHeap

A binary max-heap (priority queue).

Example

use std::collections::BinaryHeap;

let heap: BinaryHeap<i32> = BinaryHeap::new();
defer heap.free();

heap.push(2);
heap.push(9);
heap.push(5);

assert_eq!(heap.pop(), Option::some(9));
assert_eq!(heap.pop(), Option::some(5));
assert_eq!(heap.pop(), Option::some(2));
assert_eq!(heap.pop(), Option::none());
Run this example

Min-heap functionality can be achieved by using a BinaryHeap over a type that implements Comparable in reverse order.

use std::collections::BinaryHeap;
use std::cmp::{Comparable, Ordering};

struct ReversedI32 { val: i32 }

impl ReversedI32 {
    fn compare(self: &ReversedI32, other: &ReversedI32) -> Ordering {
        other.val.compare(&self.val)
    }

    mixin Comparable<ReversedI32>;
}

let heap: BinaryHeap<ReversedI32> = BinaryHeap::new();
defer heap.free();

heap.push(ReversedI32 { val: 2 });
heap.push(ReversedI32 { val: 9 });
heap.push(ReversedI32 { val: 5 });

assert_eq!(heap.pop(), Option::some(ReversedI32 { val: 2 }));
assert_eq!(heap.pop(), Option::some(ReversedI32 { val: 5 }));
assert_eq!(heap.pop(), Option::some(ReversedI32 { val: 9 }));
assert_eq!(heap.pop(), Option::none());
Run this example

Methods

• fn new() -> BinaryHeap<T>

  source

  Creates an empty binary heap.

  This will not allocate until the first element is inserted.

  Example

  use std::collections::BinaryHeap;
  
  let heap: BinaryHeap<i32> = BinaryHeap::new();
  defer heap.free();
  
  assert_eq!(heap.is_empty(), true);
  Run this example

• fn with_capacity(capacity: usize) -> BinaryHeap<T>

  source

  Create a heap that can accept at least capacity elements without reallocating.

  Example

  use std::collections::BinaryHeap;
  
  let heap: BinaryHeap<i32> = BinaryHeap::with_capacity(8);
  defer heap.free();
  
  assert!(heap.capacity() >= 8);
  Run this example

• fn from_vector(vector: Vector<T>) -> BinaryHeap<T>

  source

  Creates a heap from an existing vector.

  The vector will be heapified in-place.

  Example

  use std::collections::{BinaryHeap, Vector};
  
  let vec = Vector::from_slice(&[1, 4, 6, 7, 2, 9, 2]);
  let heap = BinaryHeap::from_vector(vec);
  defer heap.free();
  
  assert_eq!(heap.pop(), Option::some(9));
  Run this example

• fn from_vector_raw(vector: Vector<T>) -> BinaryHeap<T>

  source

  Creates a heap from an existing vector.

  The vector is assumed to satisfy the max heap property a[i] <= a[(i-1)/2]. If it does not, the behavior is unspecified.

  Example

  use std::collections::{BinaryHeap, Vector};
  
  let vec = Vector::from_slice(&[1, 2, 3]);
  let heap = BinaryHeap::from_vector_raw(vec);
  defer heap.free();
  
  assert_eq!(heap.pop(), Option::some(1)); // ???
  Run this example

• fn from_slice(slice: &[T]) -> BinaryHeap<T>

  source

  Creates a heap from a slice of elements.

  The elements are copied into the heap and heapified.

  Example

  use std::collections::BinaryHeap;
  
  let heap = BinaryHeap::from_slice(&[4, 4, 6, 7, 2, 9, 2]);
  defer heap.free();
  
  assert_eq!(heap.pop(), Option::some(9));
  Run this example

• fn from_iter<I>(iter: &mut I) -> BinaryHeap<T>

  I: Iterator<I, T>

  source

  Creates a heap from an iterator.

  Example

  use std::collections::BinaryHeap;
  
  let heap: BinaryHeap<i32> = BinaryHeap::from_iter(&(1..5));
  defer heap.free();
  
  assert_eq!(heap.pop(), Option::some(4));
  Run this example

• fn reserve(self: &mut BinaryHeap<T>, additional: usize)

  source

  Reserves capacity for at least additional more elements to be inserted without reallocating.

  Does nothing if the capacity is already sufficient.

  Example

  use std::collections::BinaryHeap;
  
  let heap: BinaryHeap<i32> = BinaryHeap::new();
  defer heap.free();
  
  heap.reserve(1000); // pre-allocate space for 1000 more elements
  
  for i in (1..1000) {
      heap.push(i); // won't reallocate
  }
  Run this example

• fn capacity(self: &BinaryHeap<T>) -> usize

  source

  Returns the maximum number of elements the heap can hold without reallocating.

  Example

  use std::collections::BinaryHeap;
  
  let heap: BinaryHeap<i32> = BinaryHeap::with_capacity(100);
  defer heap.free();
  
  let i = 0;
  while heap.len() < heap.capacity() {
      heap.push(i);
      i += 1;
  }
  Run this example

• fn is_empty(self: &BinaryHeap<T>) -> bool

  source

  Returns true if the heap contains no elements.

• fn len(self: &BinaryHeap<T>) -> usize

  source

  Returns the number of elements in the heap.

  Example

  use std::collections::BinaryHeap;
  
  let heap: BinaryHeap<i32> = BinaryHeap::new();
  defer heap.free();
  
  assert_eq!(heap.len(), 0);
  
  heap.push(3);
  heap.push(6);
  assert_eq!(heap.len(), 2);
  Run this example

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

  I: Iterator<I, T>

  source

  Extends the heap from an iterator.

  Example

  use std::collections::BinaryHeap;
  
  let heap: BinaryHeap<i32> = BinaryHeap::new();
  defer heap.free();
  
  heap.extend(&(1..5));
  assert_eq!(heap.len(), 4);
  Run this example

• fn extend_from_slice(self: &mut BinaryHeap<T>, slice: &[T])

  source

  Extends the heap from a slice of elements.

  Example

  use std::collections::BinaryHeap;
  
  let heap: BinaryHeap<i32> = BinaryHeap::new();
  defer heap.free();
  
  heap.extend_from_slice(&[1, 2, 3, 4]);
  heap.extend_from_slice(&[5, 6, 7, 8]);
  assert_eq!(heap.len(), 8);
  Run this example

• fn push(self: &mut BinaryHeap<T>, value: T)

  source

  Inserts an element into the heap.

  Example

  use std::collections::BinaryHeap;
  
  let heap: BinaryHeap<i32> = BinaryHeap::new();
  defer heap.free();
  
  heap.push(3);
  Run this example

• fn peek(self: &BinaryHeap<T>) -> Option<T>

  source

  Returns the largest element in the heap without removing it.

  Returns Option::none() if the heap is empty.

  Example

  use std::collections::BinaryHeap;
  
  let heap: BinaryHeap<i32> = BinaryHeap::new();
  defer heap.free();
  
  assert_eq!(heap.peek(), Option::none());
  heap.push(3);
  heap.push(7);
  assert_eq!(heap.peek(), Option::some(7));
  assert_eq!(heap.peek(), Option::some(7));
  assert_eq!(heap.len(), 2);
  Run this example

• fn pop(self: &mut BinaryHeap<T>) -> Option<T>

  source

  Removes the maximum element in the heap, returning it.

  Returns Option::none() if the heap is empty.

  Example

  use std::collections::BinaryHeap;
  
  let heap: BinaryHeap<i32> = BinaryHeap::new();
  defer heap.free();
  
  heap.push(3);
  heap.push(5);
  assert_eq!(heap.pop(), Option::some(5));
  Run this example

• fn shrink_to_fit(self: &mut BinaryHeap<T>)

  source

  Shrink the size of the underlying buffer to the minimum size needed to hold the current elements.

  Example

  use std::collections::BinaryHeap;
  
  let heap: BinaryHeap<i32> = BinaryHeap::with_capacity(100000);
  defer heap.free();
  
  heap.push(3);
  heap.shrink_to_fit();
  
  assert!(heap.capacity() == 1);
  Run this example

• fn retain<F>(self: &mut BinaryHeap<T>, f: F)

  F: Fn(&T) -> bool

  source

  Removes the elements not mathing the given predicate.

  The heap property is maintained after the operation.

  Does not remove excess capacity, call shrink_to_fit afterwards, if this is desired.

• fn iter(self: &BinaryHeap<T>) -> SliceIterator<&T>

  source

  Returns an iterator over the elements in the heap.

  The iterator will return the elements in arbitrary order (satisfying the heap property).

  See iter_drain for an iterator that removes the elements from the heap, but in descending order.

• fn iter_ref(self: &BinaryHeap<T>) -> SliceRefIterator<&T>

  source

  Returns a iterator over the pointers to elements in the heap.

  The iterator will return the elements in arbitrary order (satisfying the heap property).

  See iter_drain for an iterator that removes the elements from the heap, but in descending order.

• fn as_slice(self: &BinaryHeap<T>) -> &[T]

  source

  Returns the contents of the object as a slice.

  See AsSlice for details.

• fn into_vector(self: &mut BinaryHeap<T>) -> Vector<T>

  source

  Converts the heap into the underlying vector. The elements are in no particular order (satisfying the heap property).

  self is emptied after this operation (like after move).

  Example

  use std::collections::BinaryHeap;
  
  let heap: BinaryHeap<i32> = BinaryHeap::new();
  defer heap.free();
  
  heap.push(3);
  heap.push(0);
  heap.push(6);
  
  let vec = heap.into_vector();
  defer vec.free();
  
  assert_eq!(vec.len(), 3);
  assert_eq!(heap.len(), 0);
  Run this example

• fn into_vector_sorted(self: &mut BinaryHeap<T>) -> Vector<T>

  source

  Converts the heap into the underlying vector. The elements are additionally sorted in ascending order.

  self is emptied after this operation (like after move).

  Example

  use std::collections::BinaryHeap;
  
  let heap: BinaryHeap<i32> = BinaryHeap::from_slice(&[5, 3, 4, 1, 2]);
  defer heap.free();
  
  let vec = heap.into_vector_sorted();
  defer vec.free();
  
  assert_eq!(vec[..], &[1, 2, 3, 4, 5]);
  Run this example

• fn clear(self: &mut BinaryHeap<T>)

  source

  Clears the heap, removing all values.

  This does not reduce the capacity of the heap (use shrink_to_fit afterwards or use move instead).

  Example

  use std::collections::BinaryHeap;
  
  let heap: BinaryHeap<i32> = BinaryHeap::new();
  defer heap.free();
  
  heap.push(3);
  heap.push(5);
  heap.clear();
  
  assert_eq!(heap.len(), 0);
  Run this example

• fn iter_drain(self: &mut BinaryHeap<T>) -> HeapIterator<T>

  source

  Returns an iterator that removes all elements from the heap and yields them in sorted order (descending).

  Example

  use std::collections::BinaryHeap;
  
  let heap: BinaryHeap<i32> = BinaryHeap::from_slice(&[5, 3, 4, 1, 2]);
  defer heap.free();
  
  // Prints "5 4 3 2 1 "
  for x in heap.iter_drain() {
      print!("{} ", x);
  }
  
  assert!(heap.is_empty());
  Run this example

• fn free(self: &mut BinaryHeap<T>)

  source

  Frees the memory backing the object.

• fn free_all(self: &mut BinaryHeap<T>)

  source

  Helper for collections that own heap-allocated objects. This is used to be able to do defer col.free_all() without much boilerplate.

  Example

  use std::collections::BinaryHeap;
  use std::string::StringBuf;
  use std::fmt::format;
  
  let v: BinaryHeap<StringBuf> = BinaryHeap::new();
  defer v.free_all();
  
  for i in 1..10 {
      v.push("{} + {} = {}".format!(i, i, i + i).unwrap());
  }
  Run this example

• fn move(self: &mut BinaryHeap<T>) -> BinaryHeap<T>

  source

  Creates a copy of the object, leaving an inert object behind.

  See Movable for details.

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

  source

  Returns a copy of the object.