Creates an emptyBinaryHeap as a max-heap.

§Examples

Basic usage:

usestd::collections::BinaryHeap;letmutheap = BinaryHeap::new();heap.push(4);

Creates an emptyBinaryHeap with at least the specified capacity.

The binary heap will be able to hold at leastcapacity elements withoutreallocating. This method is allowed to allocate for more elements thancapacity. Ifcapacity is zero, the binary heap will not allocate.

§Examples

Basic usage:

usestd::collections::BinaryHeap;letmutheap = BinaryHeap::with_capacity(10);heap.push(4);

Creates an emptyBinaryHeap as a max-heap, usingA as allocator.

§Examples

Basic usage:

#![feature(allocator_api)]usestd::alloc::System;usestd::collections::BinaryHeap;letmutheap = BinaryHeap::new_in(System);heap.push(4);

Creates an emptyBinaryHeap with at least the specified capacity, usingA as allocator.

The binary heap will be able to hold at leastcapacity elements withoutreallocating. This method is allowed to allocate for more elements thancapacity. Ifcapacity is zero, the binary heap will not allocate.

§Examples

Basic usage:

#![feature(allocator_api)]usestd::alloc::System;usestd::collections::BinaryHeap;letmutheap = BinaryHeap::with_capacity_in(10, System);heap.push(4);

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

Note: If thePeekMut value is leaked, some heap elements might getleaked along with it, but the remaining elements will remain a validheap.

§Examples

Basic usage:

usestd::collections::BinaryHeap;letmutheap = BinaryHeap::new();assert!(heap.peek_mut().is_none());heap.push(1);heap.push(5);heap.push(2);if letSome(mutval) = heap.peek_mut() {*val =0;}assert_eq!(heap.peek(),Some(&2));

§Time complexity

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

Removes the greatest item from the binary heap and returns it, orNone if itis empty.

§Examples

Basic usage:

usestd::collections::BinaryHeap;letmutheap = BinaryHeap::from([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 ofpop on a heap containingn elements isO(log(n)).

Pushes an item onto the binary heap.

§Examples

Basic usage:

usestd::collections::BinaryHeap;letmutheap = 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 ofpush, averaged over every possible ordering ofthe elements being pushed, and over a sufficiently large number ofpushes, isO(1). This is the most meaningful cost metric when pushingelements that arenot already in any sorted pattern.

The time complexity degrades if elements are pushed in predominantlyascending order. In the worst case, elements are pushed in ascendingsorted order and the amortized cost per push isO(log(n)) against a heapcontainingn elements.

The worst case cost of asingle call topush isO(n). The worst caseoccurs when capacity is exhausted and needs a resize. The resize costhas been amortized in the previous figures.

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

§Examples

Basic usage:

usestd::collections::BinaryHeap;letmutheap = BinaryHeap::from([1,2,4,5,7]);heap.push(6);heap.push(3);letvec = heap.into_sorted_vec();assert_eq!(vec, [1,2,3,4,5,6,7]);

Moves all the elements ofother intoself, leavingother empty.

§Examples

Basic usage:

usestd::collections::BinaryHeap;letmuta = BinaryHeap::from([-10,1,2,3,3]);letmutb = BinaryHeap::from([-20,5,43]);a.append(&mutb);assert_eq!(a.into_sorted_vec(), [-20, -10,1,2,3,3,5,43]);assert!(b.is_empty());

Clears the binary heap, returning an iterator over the removed elementsin heap order. If the iterator is dropped before being fully consumed,it drops the remaining elements in heap order.

The returned iterator keeps a mutable borrow on the heap to optimizeits implementation.

Note:

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

§Examples

Basic usage:

#![feature(binary_heap_drain_sorted)]usestd::collections::BinaryHeap;letmutheap = BinaryHeap::from([1,2,3,4,5]);assert_eq!(heap.len(),5);drop(heap.drain_sorted());// removes all elements in heap orderassert_eq!(heap.len(),0);

Retains only the elements specified by the predicate.

In other words, remove all elementse for whichf(&e) returnsfalse. The elements are visited in unsorted (and unspecified) order.

§Examples

Basic usage:

usestd::collections::BinaryHeap;letmutheap = BinaryHeap::from([-10, -5,1,2,4,13]);heap.retain(|x| x %2==0);// only keep even numbersassert_eq!(heap.into_sorted_vec(), [-10,2,4])

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

§Examples

Basic usage:

usestd::collections::BinaryHeap;letheap = BinaryHeap::from([1,2,3,4]);// Print 1, 2, 3, 4 in arbitrary orderforxinheap.iter() {println!("{x}");}

Returns an iterator which retrieves elements in heap order.

This method consumes the original heap.

§Examples

Basic usage:

#![feature(binary_heap_into_iter_sorted)]usestd::collections::BinaryHeap;letheap = BinaryHeap::from([1,2,3,4,5]);assert_eq!(heap.into_iter_sorted().take(2).collect::<Vec<_>>(), [5,4]);

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

§Examples

Basic usage:

usestd::collections::BinaryHeap;letmutheap = 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 isO(1) in the worst case.

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

§Examples

Basic usage:

usestd::collections::BinaryHeap;letmutheap = BinaryHeap::with_capacity(100);assert!(heap.capacity() >=100);heap.push(4);

Reserves the minimum capacity for at leastadditional elements more thanthe current length. Unlikereserve, this will notdeliberately over-allocate to speculatively avoid frequent allocations.After callingreserve_exact, capacity will be greater than or equal toself.len() + additional. Does nothing if the capacity is alreadysufficient.

§Panics

Panics if the new capacity overflowsusize.

§Examples

Basic usage:

usestd::collections::BinaryHeap;letmutheap = BinaryHeap::new();heap.reserve_exact(100);assert!(heap.capacity() >=100);heap.push(4);

Reserves capacity for at leastadditional elements more than thecurrent length. The allocator may reserve more space to speculativelyavoid frequent allocations. After callingreserve,capacity will be greater than or equal toself.len() + additional.Does nothing if capacity is already sufficient.

§Panics

Panics if the new capacity overflowsusize.

§Examples

Basic usage:

usestd::collections::BinaryHeap;letmutheap = BinaryHeap::new();heap.reserve(100);assert!(heap.capacity() >=100);heap.push(4);

Tries to reserve the minimum capacity for at leastadditional elementsmore than the current length. Unliketry_reserve, this will notdeliberately over-allocate to speculatively avoid frequent allocations.After callingtry_reserve_exact, capacity will be greater than orequal toself.len() + additional if it returnsOk(()).Does nothing if the capacity is already sufficient.

Note that the allocator may give the collection more space than itrequests. Therefore, capacity can not be relied upon to be preciselyminimal. Prefertry_reserve if future insertions are expected.

§Errors

If the capacity overflows, or the allocator reports a failure, then an erroris returned.

§Examples

usestd::collections::BinaryHeap;usestd::collections::TryReserveError;fnfind_max_slow(data:&[u32]) ->Result<Option<u32>, TryReserveError> {letmutheap = BinaryHeap::new();// Pre-reserve the memory, exiting if we can'theap.try_reserve_exact(data.len())?;// Now we know this can't OOM in the middle of our complex workheap.extend(data.iter());Ok(heap.pop())}

Tries to reserve capacity for at leastadditional elements more than thecurrent length. The allocator may reserve more space to speculativelyavoid frequent allocations. After callingtry_reserve, capacity will begreater than or equal toself.len() + additional if it returnsOk(()). Does nothing if capacity is already sufficient. This methodpreserves the contents even if an error occurs.

§Errors

If the capacity overflows, or the allocator reports a failure, then an erroris returned.

§Examples

usestd::collections::BinaryHeap;usestd::collections::TryReserveError;fnfind_max_slow(data:&[u32]) ->Result<Option<u32>, TryReserveError> {letmutheap = BinaryHeap::new();// Pre-reserve the memory, exiting if we can'theap.try_reserve(data.len())?;// Now we know this can't OOM in the middle of our complex workheap.extend(data.iter());Ok(heap.pop())}

Discards as much additional capacity as possible.

§Examples

Basic usage:

usestd::collections::BinaryHeap;letmutheap: 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 lengthand the supplied value.

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

§Examples

usestd::collections::BinaryHeap;letmutheap: BinaryHeap<i32> = BinaryHeap::with_capacity(100);assert!(heap.capacity() >=100);heap.shrink_to(10);assert!(heap.capacity() >=10);

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

§Examples

Basic usage:

usestd::collections::BinaryHeap;usestd::io::{self, Write};letheap = BinaryHeap::from([1,2,3,4,5,6,7]);io::sink().write(heap.as_slice()).unwrap();

Consumes theBinaryHeap and returns the underlying vectorin arbitrary order.

§Examples

Basic usage:

usestd::collections::BinaryHeap;letheap = BinaryHeap::from([1,2,3,4,5,6,7]);letvec = heap.into_vec();// Will print in some orderforxinvec {println!("{x}");}

Returns a reference to the underlying allocator.

Returns the length of the binary heap.

§Examples

Basic usage:

usestd::collections::BinaryHeap;letheap = BinaryHeap::from([1,3]);assert_eq!(heap.len(),2);

Checks if the binary heap is empty.

§Examples

Basic usage:

usestd::collections::BinaryHeap;letmutheap = 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 elementsin arbitrary order. If the iterator is dropped before being fullyconsumed, it drops the remaining elements in arbitrary order.

The returned iterator keeps a mutable borrow on the heap to optimizeits implementation.

§Examples

Basic usage:

usestd::collections::BinaryHeap;letmutheap = BinaryHeap::from([1,3]);assert!(!heap.is_empty());forxinheap.drain() {println!("{x}");}assert!(heap.is_empty());

Drops all items from the binary heap.

§Examples

Basic usage:

usestd::collections::BinaryHeap;letmutheap = BinaryHeap::from([1,3]);assert!(!heap.is_empty());heap.clear();assert!(heap.is_empty());

Overwrites the contents ofself with a clone of the contents ofsource.

This method is preferred over simply assigningsource.clone() toself,as it avoids reallocation if possible.

SeeVec::clone_from() for more details.

Creates an emptyBinaryHeap<T>.

Converts aBinaryHeap<T> into aVec<T>.

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

Converts aVec<T> into aBinaryHeap<T>.

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

Creates a consuming iterator, that is, one that moves each value out ofthe binary heap in arbitrary order. The binary heap cannot be usedafter calling this.

§Examples

Basic usage:

usestd::collections::BinaryHeap;letheap = BinaryHeap::from([1,2,3,4]);// Print 1, 2, 3, 4 in arbitrary orderforxinheap.into_iter() {// x has type i32, not &i32println!("{x}");}

Returns the argument unchanged.

CallsU::from(self).

That is, this conversion is whatever the implementation ofFrom<T> for U chooses to do.