Struct scale_info::prelude::collections::BinaryHeap1.0.0[][src]

pub struct BinaryHeap<T> { /* fields omitted */ }
Expand description

A priority queue implemented with a binary heap.

This will be a max-heap.

It is a logic error for an item to be modified in such a way that the item’s ordering relative to any other item, as determined by the Ord trait, changes while it is in the heap. This is normally only possible through Cell, RefCell, global state, I/O, or unsafe code. The behavior resulting from such a logic error is not specified, but will not result in undefined behavior. This could include panics, incorrect results, aborts, memory leaks, and non-termination.

Examples

use std::collections::BinaryHeap;

// Type inference lets us omit an explicit type signature (which
// would be `BinaryHeap<i32>` in this example).
let mut heap = BinaryHeap::new();

// We can use peek to look at the next item in the heap. In this case,
// there's no items in there yet so we get None.
assert_eq!(heap.peek(), None);

// Let's add some scores...
heap.push(1);
heap.push(5);
heap.push(2);

// Now peek shows the most important item in the heap.
assert_eq!(heap.peek(), Some(&5));

// We can check the length of a heap.
assert_eq!(heap.len(), 3);

// We can iterate over the items in the heap, although they are returned in
// a random order.
for x in &heap {
    println!("{}", x);
}

// If we instead pop these scores, they should come back in order.
assert_eq!(heap.pop(), Some(5));
assert_eq!(heap.pop(), Some(2));
assert_eq!(heap.pop(), Some(1));
assert_eq!(heap.pop(), None);

// We can clear the heap of any remaining items.
heap.clear();

// The heap should now be empty.
assert!(heap.is_empty())

A BinaryHeap with a known list of items can be initialized from an array:

use std::collections::BinaryHeap;

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

Min-heap

Either std::cmp::Reverse or a custom Ord implementation can be used to make BinaryHeap a min-heap. This makes heap.pop() return the smallest value instead of the greatest one.

use std::collections::BinaryHeap;
use std::cmp::Reverse;

let mut heap = BinaryHeap::new();

// Wrap values in `Reverse`
heap.push(Reverse(1));
heap.push(Reverse(5));
heap.push(Reverse(2));

// If we pop these scores now, they should come back in the reverse order.
assert_eq!(heap.pop(), Some(Reverse(1)));
assert_eq!(heap.pop(), Some(Reverse(2)));
assert_eq!(heap.pop(), Some(Reverse(5)));
assert_eq!(heap.pop(), None);

Time complexity

pushpoppeek/peek_mut
O(1)~O(log(n))O(1)

The value for push is an expected cost; the method documentation gives a more detailed analysis.

Implementations

Creates an empty BinaryHeap as a max-heap.

Examples

Basic usage:

use std::collections::BinaryHeap;
let mut heap = BinaryHeap::new();
heap.push(4);

Creates an empty BinaryHeap with a specific capacity. This preallocates enough memory for capacity elements, so that the BinaryHeap does not have to be reallocated until it contains at least that many values.

Examples

Basic usage:

use std::collections::BinaryHeap;
let mut heap = BinaryHeap::with_capacity(10);
heap.push(4);

Returns a mutable reference to the greatest item in the binary heap, or None if it is empty.

Note: If the PeekMut value is leaked, the heap may be in an inconsistent state.

Examples

Basic usage:

use std::collections::BinaryHeap;
let mut heap = BinaryHeap::new();
assert!(heap.peek_mut().is_none());

heap.push(1);
heap.push(5);
heap.push(2);
{
    let mut val = heap.peek_mut().unwrap();
    *val = 0;
}
assert_eq!(heap.peek(), Some(&2));

Time complexity

If the item is modified then the worst case time complexity is O(log(n)), otherwise it’s O(1).

Removes the greatest item from the binary heap and returns it, or None if it is empty.

Examples

Basic usage:

use std::collections::BinaryHeap;
let mut heap = BinaryHeap::from(vec![1, 3]);

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

Time complexity

The worst case cost of pop on a heap containing n elements is O(log(n)).

Pushes an item onto the binary heap.

Examples

Basic usage:

use std::collections::BinaryHeap;
let mut heap = BinaryHeap::new();
heap.push(3);
heap.push(5);
heap.push(1);

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

Time complexity

The expected cost of push, averaged over every possible ordering of the elements being pushed, and over a sufficiently large number of pushes, is O(1). This is the most meaningful cost metric when pushing elements that are not already in any sorted pattern.

The time complexity degrades if elements are pushed in predominantly ascending order. In the worst case, elements are pushed in ascending sorted order and the amortized cost per push is O(log(n)) against a heap containing n elements.

The worst case cost of a single call to push is O(n). The worst case occurs when capacity is exhausted and needs a resize. The resize cost has been amortized in the previous figures.

Consumes the BinaryHeap and returns a vector in sorted (ascending) order.

Examples

Basic usage:

use std::collections::BinaryHeap;

let mut heap = BinaryHeap::from(vec![1, 2, 4, 5, 7]);
heap.push(6);
heap.push(3);

let vec = heap.into_sorted_vec();
assert_eq!(vec, [1, 2, 3, 4, 5, 6, 7]);

Moves all the elements of other into self, leaving other empty.

Examples

Basic usage:

use std::collections::BinaryHeap;

let v = vec![-10, 1, 2, 3, 3];
let mut a = BinaryHeap::from(v);

let v = vec![-20, 5, 43];
let mut b = BinaryHeap::from(v);

a.append(&mut b);

assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
assert!(b.is_empty());
🔬 This is a nightly-only experimental API. (binary_heap_drain_sorted)

Returns an iterator which retrieves elements in heap order. The retrieved elements are removed from the original heap. The remaining elements will be removed on drop in heap order.

Note:

  • .drain_sorted() is O(n * log(n)); much slower than .drain(). You should use the latter for most cases.

Examples

Basic usage:

#![feature(binary_heap_drain_sorted)]
use std::collections::BinaryHeap;

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

drop(heap.drain_sorted()); // removes all elements in heap order
assert_eq!(heap.len(), 0);
🔬 This is a nightly-only experimental API. (binary_heap_retain)

Retains only the elements specified by the predicate.

In other words, remove all elements e such that f(&e) returns false. The elements are visited in unsorted (and unspecified) order.

Examples

Basic usage:

#![feature(binary_heap_retain)]
use std::collections::BinaryHeap;

let mut heap = BinaryHeap::from(vec![-10, -5, 1, 2, 4, 13]);

heap.retain(|x| x % 2 == 0); // only keep even numbers

assert_eq!(heap.into_sorted_vec(), [-10, 2, 4])

Returns an iterator visiting all values in the underlying vector, in arbitrary order.

Examples

Basic usage:

use std::collections::BinaryHeap;
let heap = BinaryHeap::from(vec![1, 2, 3, 4]);

// Print 1, 2, 3, 4 in arbitrary order
for x in heap.iter() {
    println!("{}", x);
}
🔬 This is a nightly-only experimental API. (binary_heap_into_iter_sorted)

Returns an iterator which retrieves elements in heap order. This method consumes the original heap.

Examples

Basic usage:

#![feature(binary_heap_into_iter_sorted)]
use std::collections::BinaryHeap;
let heap = BinaryHeap::from(vec![1, 2, 3, 4, 5]);

assert_eq!(heap.into_iter_sorted().take(2).collect::<Vec<_>>(), vec![5, 4]);

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

Examples

Basic usage:

use std::collections::BinaryHeap;
let mut heap = BinaryHeap::new();
assert_eq!(heap.peek(), None);

heap.push(1);
heap.push(5);
heap.push(2);
assert_eq!(heap.peek(), Some(&5));

Time complexity

Cost is O(1) in the worst case.

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

Examples

Basic usage:

use std::collections::BinaryHeap;
let mut heap = BinaryHeap::with_capacity(100);
assert!(heap.capacity() >= 100);
heap.push(4);

Reserves the minimum capacity for exactly additional more elements to be inserted in the given BinaryHeap. Does nothing if the capacity is already sufficient.

Note that the allocator may give the collection more space than it requests. Therefore capacity can not be relied upon to be precisely minimal. Prefer reserve if future insertions are expected.

Panics

Panics if the new capacity overflows usize.

Examples

Basic usage:

use std::collections::BinaryHeap;
let mut heap = BinaryHeap::new();
heap.reserve_exact(100);
assert!(heap.capacity() >= 100);
heap.push(4);

Reserves capacity for at least additional more elements to be inserted in the BinaryHeap. The collection may reserve more space to avoid frequent reallocations.

Panics

Panics if the new capacity overflows usize.

Examples

Basic usage:

use std::collections::BinaryHeap;
let mut heap = BinaryHeap::new();
heap.reserve(100);
assert!(heap.capacity() >= 100);
heap.push(4);

Discards as much additional capacity as possible.

Examples

Basic usage:

use std::collections::BinaryHeap;
let mut heap: BinaryHeap<i32> = BinaryHeap::with_capacity(100);

assert!(heap.capacity() >= 100);
heap.shrink_to_fit();
assert!(heap.capacity() == 0);

Discards capacity with a lower bound.

The capacity will remain at least as large as both the length and the supplied value.

If the current capacity is less than the lower limit, this is a no-op.

Examples

use std::collections::BinaryHeap;
let mut heap: BinaryHeap<i32> = BinaryHeap::with_capacity(100);

assert!(heap.capacity() >= 100);
heap.shrink_to(10);
assert!(heap.capacity() >= 10);
🔬 This is a nightly-only experimental API. (binary_heap_as_slice)

Returns a slice of all values in the underlying vector, in arbitrary order.

Examples

Basic usage:

#![feature(binary_heap_as_slice)]
use std::collections::BinaryHeap;
use std::io::{self, Write};

let heap = BinaryHeap::from(vec![1, 2, 3, 4, 5, 6, 7]);

io::sink().write(heap.as_slice()).unwrap();

Consumes the BinaryHeap and returns the underlying vector in arbitrary order.

Examples

Basic usage:

use std::collections::BinaryHeap;
let heap = BinaryHeap::from(vec![1, 2, 3, 4, 5, 6, 7]);
let vec = heap.into_vec();

// Will print in some order
for x in vec {
    println!("{}", x);
}

Returns the length of the binary heap.

Examples

Basic usage:

use std::collections::BinaryHeap;
let heap = BinaryHeap::from(vec![1, 3]);

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

Checks if the binary heap is empty.

Examples

Basic usage:

use std::collections::BinaryHeap;
let mut heap = BinaryHeap::new();

assert!(heap.is_empty());

heap.push(3);
heap.push(5);
heap.push(1);

assert!(!heap.is_empty());

Clears the binary heap, returning an iterator over the removed elements.

The elements are removed in arbitrary order.

Examples

Basic usage:

use std::collections::BinaryHeap;
let mut heap = BinaryHeap::from(vec![1, 3]);

assert!(!heap.is_empty());

for x in heap.drain() {
    println!("{}", x);
}

assert!(heap.is_empty());

Drops all items from the binary heap.

Examples

Basic usage:

use std::collections::BinaryHeap;
let mut heap = BinaryHeap::from(vec![1, 3]);

assert!(!heap.is_empty());

heap.clear();

assert!(heap.is_empty());

Trait Implementations

Returns a copy of the value. Read more

Performs copy-assignment from source. Read more

Formats the value using the given formatter. Read more

Attempt to deserialise the value from input.

Attempt to skip the encoded value from input. Read more

Returns the fixed encoded size of the type. Read more

Return the number of elements in self_encoded.

Creates an empty BinaryHeap<T>.

Deserialize this value from the given Serde deserializer. Read more

If possible give a hint of expected size of the encoding. Read more

Convert self to a slice and append it to the destination.

Convert self to an owned vector.

Convert self to a slice and then invoke the given closure with it.

Calculates the encoded size. Read more

Extends a collection with the contents of an iterator. Read more

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

Extends a collection with exactly one element.

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

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

Extends a collection with the contents of an iterator. Read more

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

Extends a collection with exactly one element.

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

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

use std::collections::BinaryHeap;

let mut h1 = BinaryHeap::from([1, 4, 2, 3]);
let mut h2: BinaryHeap<_> = [1, 4, 2, 3].into();
while let Some((a, b)) = h1.pop().zip(h2.pop()) {
    assert_eq!(a, b);
}

Converts a BinaryHeap<T> into a Vec<T>.

This conversion requires no data movement or allocation, and has constant time complexity.

Converts a Vec<T> into a BinaryHeap<T>.

This conversion happens in-place, and has O(n) time complexity.

Creates a value from an iterator. Read more

Creates a consuming iterator, that is, one that moves each value out of the binary heap in arbitrary order. The binary heap cannot be used after calling this.

Examples

Basic usage:

use std::collections::BinaryHeap;
let heap = BinaryHeap::from(vec![1, 2, 3, 4]);

// Print 1, 2, 3, 4 in arbitrary order
for x in heap.into_iter() {
    // x has type i32, not &i32
    println!("{}", x);
}

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

Creates an iterator from a value. Read more

Serialize this value into the given Serde serializer. Read more

Auto Trait Implementations

Blanket Implementations

Gets the TypeId of self. Read more

Immutably borrows from an owned value. Read more

Mutably borrows from an owned value. Read more

Converts self into T using Into<T>. Read more

Converts self into a target type. Read more

Decode Self and consume all of the given input data. Read more

Decode Self and consume all of the given input data. Read more

Decode Self with the given maximum recursion depth. Read more

Causes self to use its Binary implementation when Debug-formatted.

Causes self to use its Display implementation when Debug-formatted. Read more

Causes self to use its LowerExp implementation when Debug-formatted. Read more

Causes self to use its LowerHex implementation when Debug-formatted. Read more

Causes self to use its Octal implementation when Debug-formatted.

Causes self to use its Pointer implementation when Debug-formatted. Read more

Causes self to use its UpperExp implementation when Debug-formatted. Read more

Causes self to use its UpperHex implementation when Debug-formatted. Read more

Performs the conversion.

Performs the conversion.

Append encoding of value to Self.

Return an encoding of Self prepended by given slice.

Pipes by value. This is generally the method you want to use. Read more

Borrows self and passes that borrow into the pipe function. Read more

Mutably borrows self and passes that borrow into the pipe function. Read more

Borrows self, then passes self.borrow() into the pipe function. Read more

Mutably borrows self, then passes self.borrow_mut() into the pipe function. Read more

Borrows self, then passes self.as_ref() into the pipe function.

Mutably borrows self, then passes self.as_mut() into the pipe function. Read more

Borrows self, then passes self.deref() into the pipe function.

Mutably borrows self, then passes self.deref_mut() into the pipe function. Read more

Pipes a value into a function that cannot ordinarily be called in suffix position. Read more

Pipes a trait borrow into a function that cannot normally be called in suffix position. Read more

Pipes a trait mutable borrow into a function that cannot normally be called in suffix position. Read more

Pipes a trait borrow into a function that cannot normally be called in suffix position. Read more

Pipes a trait mutable borrow into a function that cannot normally be called in suffix position. Read more

Pipes a dereference into a function that cannot normally be called in suffix position. Read more

Pipes a mutable dereference into a function that cannot normally be called in suffix position. Read more

Pipes a reference into a function that cannot ordinarily be called in suffix position. Read more

Pipes a mutable reference into a function that cannot ordinarily be called in suffix position. Read more

Immutable access to a value. Read more

Mutable access to a value. Read more

Immutable access to the Borrow<B> of a value. Read more

Mutable access to the BorrowMut<B> of a value. Read more

Immutable access to the AsRef<R> view of a value. Read more

Mutable access to the AsMut<R> view of a value. Read more

Immutable access to the Deref::Target of a value. Read more

Mutable access to the Deref::Target of a value. Read more

Calls .tap() only in debug builds, and is erased in release builds.

Calls .tap_mut() only in debug builds, and is erased in release builds. Read more

Calls .tap_borrow() only in debug builds, and is erased in release builds. Read more

Calls .tap_borrow_mut() only in debug builds, and is erased in release builds. Read more

Calls .tap_ref() only in debug builds, and is erased in release builds. Read more

Calls .tap_ref_mut() only in debug builds, and is erased in release builds. Read more

Calls .tap_deref() only in debug builds, and is erased in release builds. Read more

Calls .tap_deref_mut() only in debug builds, and is erased in release builds. Read more

Provides immutable access for inspection. Read more

Calls tap in debug builds, and does nothing in release builds.

Provides mutable access for modification. Read more

Calls tap_mut in debug builds, and does nothing in release builds.

Provides immutable access to the reference for inspection.

Calls tap_ref in debug builds, and does nothing in release builds.

Provides mutable access to the reference for modification.

Calls tap_ref_mut in debug builds, and does nothing in release builds.

Provides immutable access to the borrow for inspection. Read more

Calls tap_borrow in debug builds, and does nothing in release builds.

Provides mutable access to the borrow for modification.

Calls tap_borrow_mut in debug builds, and does nothing in release builds. Read more

Immutably dereferences self for inspection.

Calls tap_deref in debug builds, and does nothing in release builds.

Mutably dereferences self for modification.

Calls tap_deref_mut in debug builds, and does nothing in release builds. Read more

The resulting type after obtaining ownership.

Creates owned data from borrowed data, usually by cloning. Read more

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

recently added

Uses borrowed data to replace owned data, usually by cloning. Read more

Attempts to convert self into T using TryInto<T>. Read more

Attempts to convert self into a target type. Read more

The type returned in the event of a conversion error.

Performs the conversion.

The type returned in the event of a conversion error.

Performs the conversion.