Struct std::collections::BinaryHeap

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

用二进制堆实现的优先级队列。

这将是一个最大的堆。

项的修改方式是一个逻辑错误，即项相对于任何其他项的排序 (由 Ord trait 确定) 在它在堆中时发生变化。这通常只能通过内部可变性、全局状态、I/O 或不安全代码实现。由这种逻辑错误导致的行为没有被指定，但会封装到观察到逻辑错误的 BinaryHeap 中，并且不会导致未定义的行为。

这可能包括 panics、不正确的结果、中止、内存泄漏和未中止。

只要元素在堆中时如上所述没有改变它们的相对顺序，BinaryHeap 的 API 就保证堆不，变体，保持不变，即它的方法都按照文档的方式运行。 例如，如果一个方法被记录为按排序顺序迭代，那么只要堆中的元素没有改变顺序，它就可以保证工作，即使存在闭包被展开、迭代器被泄漏以及类似的愚蠢行为。

Examples

use std::collections::BinaryHeap;

// 通过类型推断，我们可以省略显式类型签名 (在本示例中为 `BinaryHeap<i32>`)。
let mut heap = BinaryHeap::new();

// 我们可以使用 peek 来查看堆中的下一个项。
// 在这种情况下，那里还没有项目，所以我们得到 None。
assert_eq!(heap.peek(), None);

// 让我们添加一些分数...
heap.push(1);
heap.push(5);
heap.push(2);

// 现在，窥视显示了堆中最重要的项。
assert_eq!(heap.peek(), Some(&5));

// 我们可以检查堆的长度。
assert_eq!(heap.len(), 3);

// 我们可以遍历堆中的项，尽管它们是按随机顺序返回的。
for x in &heap {
    println!("{x}");
}

// 如果我们改为弹出这些分数，它们应该按顺序返回。
assert_eq!(heap.pop(), Some(5));
assert_eq!(heap.pop(), Some(2));
assert_eq!(heap.pop(), Some(1));
assert_eq!(heap.pop(), None);

// 我们可以清除任何剩余项的堆。
heap.clear();

// 堆现在应该为空。
assert!(heap.is_empty())

可以从数组初始化具有已知项列表的 BinaryHeap：

use std::collections::BinaryHeap;

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

Min-heap

core::cmp::Reverse 或自定义 Ord 实现可用于使 BinaryHeap 成为最小堆。这使 heap.pop() 返回最小值而不是最大值。

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

let mut heap = BinaryHeap::new();

// 在 `Reverse` 中包装值
heap.push(Reverse(1));
heap.push(Reverse(5));
heap.push(Reverse(2));

// 如果我们现在弹出这些分数，它们应该以相反的顺序返回。
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);

时间复杂度

push	pop	peek/peek_mut
O(1)~	O(log(n))	O(1)

push 的值是预期成本； 方法文档提供了更详细的分析。

Implementations

impl<T> BinaryHeap<T>where T: Ord,

pub fn new() -> BinaryHeap<T>

创建一个空的 BinaryHeap 作为最大堆。

Examples

基本用法：

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

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

创建一个至少具有指定容量的空 BinaryHeap。

二进制堆将能够保存至少 capacity 个元素而无需重新分配。 此方法允许分配比 capacity 更多的元素。 如果 capacity 为 0，则不会分配二进制堆。

Examples

基本用法：

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

pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T>>

返回二进制堆中最大项的变量引用; 如果为空，则返回 None。

Note: 如果 PeekMut 值泄漏，一些堆元素可能会随之泄漏，但其余元素将保持有效堆。

Examples

基本用法：

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));

时间复杂度

如果该项被修改，则最坏情况下的时间复杂度为 O(log(n))，否则为 O(1)。

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

从二进制堆中删除最大的项并返回它; 如果为空，则返回 None。

Examples

基本用法：

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

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

时间复杂度

pop 在包含 n 个元素的堆上的最坏情况代价是 O(log(n))。

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

将项目推入二进制堆。

Examples

基本用法：

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));

时间复杂度

push 的预期成本是 O(1)，该成本是在被推元素的每个可能排序以及足够大量的推数上平均的。

当推送尚未处于任何排序模式的元素时，这是最有意义的成本指标。

如果元素主要以升序推入，则时间复杂度会降低。 在最坏的情况下，元素以升序排序，并且每次推送的摊销成本为 O(log(n)) 对包含 n 个元素的堆。

对 push 进行 * 调用的最坏情况是 O(n)。最坏的情况发生在容量用尽并需要调整大小时。 调整大小成本已在之前的数字中摊销。

pub fn into_sorted_vec(self) -> Vec<T, Global>

消耗 BinaryHeap 并按已排序的 (ascending) 顺序返回 vector。

Examples

基本用法：

use std::collections::BinaryHeap;

let mut heap = BinaryHeap::from([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]);

pub fn append(&mut self, other: &mut BinaryHeap<T>)

将 other 的所有元素移到 self，将 other 留空。

Examples

基本用法：

use std::collections::BinaryHeap;

let mut a = BinaryHeap::from([-10, 1, 2, 3, 3]);
let mut b = BinaryHeap::from([-20, 5, 43]);

a.append(&mut b);

assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
assert!(b.is_empty());

pub fn drain_sorted(&mut self) -> DrainSorted<'_, T>

🔬This is a nightly-only experimental API. (binary_heap_drain_sorted #59278)

清除二进制堆，按堆顺序返回已删除元素的迭代器。 如果迭代器在被完全消耗之前被丢弃，它会按照堆顺序丢弃剩余的元素。

返回的迭代器在堆上保留一个可变借用以优化其实现。

Note:

• .drain_sorted() 是 O(n* log(n))； 比 .drain() 慢得多。 在大多数情况下，应使用后者。

Examples

基本用法：

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

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

drop(heap.drain_sorted()); // 删除堆顺序中的所有元素
assert_eq!(heap.len(), 0);

pub fn retain<F>(&mut self, f: F)where F: FnMut(&T) -> bool,

仅保留谓词指定的元素。

换句话说，删除所有 f(&e) 返回 false 的 e 元素。 元素以未排序 (和未指定) 的顺序访问。

Examples

基本用法：

use std::collections::BinaryHeap;

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

heap.retain(|x| x % 2 == 0); // 只保留偶数

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

impl<T> BinaryHeap<T>

pub fn iter(&self) -> Iter<'_, T>

返回一个迭代器，以任意顺序访问底层 vector 中的所有值。

Examples

基本用法：

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

// 以任意顺序打印 1，2，3，4
for x in heap.iter() {
    println!("{x}");
}

pub fn into_iter_sorted(self) -> IntoIterSorted<T>

🔬This is a nightly-only experimental API. (binary_heap_into_iter_sorted #59278)

返回一个迭代器，该迭代器以堆顺序检索元素。 此方法消耗原始堆。

Examples

基本用法：

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

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

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

返回二进制堆中最大的项，如果为空，则返回 None。

Examples

基本用法：

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));

时间复杂度

在最坏的情况下，成本为 O(1)。

pub fn capacity(&self) -> usize

返回二进制堆在不重新分配的情况下可以容纳的元素数。

Examples

基本用法：

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

pub fn reserve_exact(&mut self, additional: usize)

为超过当前长度的至少 additional 个元素保留最小容量。 与 reserve 不同，这不会故意过度分配以推测性地避免频繁分配。

调用 reserve_exact 后，容量将大于或等于 self.len() + additional。 如果容量已经足够，则不执行任何操作。

Panics

如果新容量溢出 usize，就会出现 panics。

Examples

基本用法：

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

pub fn reserve(&mut self, additional: usize)

为超过当前长度的至少 additional 个元素保留容量。分配器可以保留更多空间来推测性地避免频繁分配。

调用 reserve 后，容量将大于或等于 self.len() + additional。 如果容量已经足够，则不执行任何操作。

Panics

如果新容量溢出 usize，就会出现 panics。

Examples

基本用法：

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

pub fn try_reserve_exact( &mut self, additional: usize ) -> Result<(), TryReserveError>

尝试为超过当前长度的至少 additional 个元素保留最小容量。 与 try_reserve 不同，这不会故意过度分配以推测性地避免频繁分配。 调用 try_reserve_exact 后，如果返回 Ok(())，则容量将大于或等于 self.len() + additional。

如果容量已经足够，则不执行任何操作。

请注意，分配器可能会给集合提供比其请求更多的空间。 因此，不能依靠容量来精确地最小化。 如果希望将来插入，则首选 try_reserve。

Errors

如果容量溢出，或者分配器报告失败，则返回错误。

Examples

use std::collections::BinaryHeap;
use std::collections::TryReserveError;

fn find_max_slow(data: &[u32]) -> Result<Option<u32>, TryReserveError> {
    let mut heap = BinaryHeap::new();

    // 预先保留内存，如果不能，则退出
    heap.try_reserve_exact(data.len())?;

    // 现在我们知道在我们复杂的工作中这不能 OOM
    heap.extend(data.iter());

    Ok(heap.pop())
}

pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError>

尝试为超过当前长度的至少 additional 个元素保留容量。 分配器可以保留更多空间来推测性地避免频繁分配。 调用 try_reserve 后，如果返回 Ok(())，容量将大于等于 self.len() + additional。

如果容量已经足够，则不执行任何操作。 即使发生错误，此方法也会保留内容。

Errors

如果容量溢出，或者分配器报告失败，则返回错误。

Examples

use std::collections::BinaryHeap;
use std::collections::TryReserveError;

fn find_max_slow(data: &[u32]) -> Result<Option<u32>, TryReserveError> {
    let mut heap = BinaryHeap::new();

    // 预先保留内存，如果不能，则退出
    heap.try_reserve(data.len())?;

    // 现在我们知道在我们复杂的工作中这不能 OOM
    heap.extend(data.iter());

    Ok(heap.pop())
}

pub fn shrink_to_fit(&mut self)

丢弃尽可能多的附加容量。

Examples

基本用法：

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);

pub fn shrink_to(&mut self, min_capacity: usize)

丢弃容量下限。

容量将至少保持与长度和提供的值一样大。

如果当前容量小于下限，则为无操作。

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);

pub fn as_slice(&self) -> &[T]

🔬This is a nightly-only experimental API. (binary_heap_as_slice #83659)

以任意顺序返回底层 vector 中所有值的切片。

Examples

基本用法：

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

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

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

pub fn into_vec(self) -> Vec<T, Global>

消耗 BinaryHeap 并以任意顺序返回底层 vector。

Examples

基本用法：

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

// 将以一定顺序打印
for x in vec {
    println!("{x}");
}

pub fn len(&self) -> usize

返回二进制堆的长度。

Examples

基本用法：

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

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

pub fn is_empty(&self) -> bool

检查二进制堆是否为空。

Examples

基本用法：

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());

pub fn drain(&mut self) -> Drain<'_, T>

清除二进制堆，以任意顺序返回已删除元素的迭代器。 如果迭代器在被完全消耗之前被丢弃，它会以任意顺序丢弃剩余的元素。

返回的迭代器在堆上保留一个可变借用以优化其实现。

Examples

基本用法：

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

assert!(!heap.is_empty());

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

assert!(heap.is_empty());

pub fn clear(&mut self)

从二进制堆中丢弃所有项。

Examples

基本用法：

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

assert!(!heap.is_empty());

heap.clear();

assert!(heap.is_empty());

Trait Implementations

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

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

返回值的副本。

fn clone_from(&mut self, source: &BinaryHeap<T>)

从 source 执行复制分配。

impl<T> Debug for BinaryHeap<T>where T: Debug,

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

使用给定的格式化程序格式化该值。

impl<T> Default for BinaryHeap<T>where T: Ord,

fn default() -> BinaryHeap<T>

创建一个空的 BinaryHeap<T>。

impl<'a, T> Extend<&'a T> for BinaryHeap<T>where T: 'a + Ord + Copy,

fn extend<I>(&mut self, iter: I)where I: IntoIterator<Item = &'a T>,

使用迭代器的内容扩展集合。

fn extend_one(&mut self, _: &'a T)

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

用一个元素扩展一个集合。

fn extend_reserve(&mut self, additional: usize)

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

在集合中为给定数量的附加元素保留容量。

impl<T> Extend<T> for BinaryHeap<T>where T: Ord,

fn extend<I>(&mut self, iter: I)where I: IntoIterator<Item = T>,

使用迭代器的内容扩展集合。

fn extend_one(&mut self, item: T)

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

用一个元素扩展一个集合。

fn extend_reserve(&mut self, additional: usize)

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

在集合中为给定数量的附加元素保留容量。

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

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

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);
}

impl<T> From<BinaryHeap<T>> for Vec<T, Global>

fn from(heap: BinaryHeap<T>) -> Vec<T, Global>

将 BinaryHeap<T> 转换为 Vec<T>。

这种转换不需要数据移动或分配，并且具有恒定的时间复杂度。

impl<T> From<Vec<T, Global>> for BinaryHeap<T>where T: Ord,

fn from(vec: Vec<T, Global>) -> BinaryHeap<T>

将 Vec<T> 转换为 BinaryHeap<T>。

此转换发生在原地，并且具有 O(n) 时间复杂度。

impl<T> FromIterator<T> for BinaryHeap<T>where T: Ord,

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

从迭代器创建一个值。

impl<'a, T> IntoIterator for &'a BinaryHeap<T>

type Item = &'a T

被迭代的元素的类型。

type IntoIter = Iter<'a, T>

我们将其变成哪种迭代器？

fn into_iter(self) -> Iter<'a, T>

从一个值创建一个迭代器。

impl<T> IntoIterator for BinaryHeap<T>

fn into_iter(self) -> IntoIter<T>

创建一个消耗迭代器，即一个将任意值以任意顺序移出二进制堆的迭代器。 调用此后不能使用二进制堆。

Examples

基本用法：

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

// 以任意顺序打印 1，2，3，4
for x in heap.into_iter() {
    // x 的类型为 i32，不是 &i32
    println!("{x}");
}

type Item = T

被迭代的元素的类型。

type IntoIter = IntoIter<T>

我们将其变成哪种迭代器？