Struct std::collections::BinaryHeap

1.0.0 · source ·
pub struct BinaryHeap<T> { /* private fields */ }
Expand description

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

这将是一个最大的堆。

项的修改方式是一个逻辑错误,即项相对于任何其他项的排序 (由 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())
Run

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

use std::collections::BinaryHeap;

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

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

时间复杂度

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

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

Implementations§

source§

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

source

pub fn new() -> BinaryHeap<T>

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

Examples

基本用法:

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

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);
Run
1.12.0 · source

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));
Run
时间复杂度

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

source

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);
Run
时间复杂度

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

source

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));
Run
时间复杂度

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

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

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

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

1.5.0 · source

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]);
Run
1.11.0 · source

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

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);
Run
1.70.0 · source

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

仅保留谓词指定的元素。

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

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])
Run
source§

impl<T> BinaryHeap<T>

source

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}");
}
Run
source

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]);
Run
source

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));
Run
时间复杂度

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

source

pub fn capacity(&self) -> usize

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

Examples

基本用法:

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

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

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);
Run
1.63.0 · source

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())
}
Run
1.63.0 · source

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())
}
Run
source

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);
Run
1.56.0 · source

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

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();
Run
1.5.0 · source

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}");
}
Run
source

pub fn len(&self) -> usize

返回二进制堆的长度。

Examples

基本用法:

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

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

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());
Run
1.6.0 · source

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

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

Trait Implementations§

source§

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

source§

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

返回值的副本。 Read more
source§

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

source 执行复制分配。 Read more
1.4.0 · source§

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

source§

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

使用给定的格式化程序格式化该值。 Read more
source§

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

source§

fn default() -> BinaryHeap<T>

创建一个空的 BinaryHeap<T>

1.2.0 · source§

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

source§

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

使用迭代器的内容扩展集合。 Read more
source§

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

🔬This is a nightly-only experimental API. (extend_one #72631)
用一个元素扩展一个集合。
source§

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one #72631)
在集合中为给定数量的附加元素保留容量。 Read more
source§

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

source§

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

使用迭代器的内容扩展集合。 Read more
source§

fn extend_one(&mut self, item: T)

🔬This is a nightly-only experimental API. (extend_one #72631)
用一个元素扩展一个集合。
source§

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one #72631)
在集合中为给定数量的附加元素保留容量。 Read more
1.56.0 · source§

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

source§

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);
}
Run
1.5.0 · source§

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

source§

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

BinaryHeap<T> 转换为 Vec<T>

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

1.5.0 · source§

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

source§

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

Vec<T> 转换为 BinaryHeap<T>

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

source§

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

source§

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

从迭代器创建一个值。 Read more
source§

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

§

type Item = &'a T

被迭代的元素的类型。
§

type IntoIter = Iter<'a, T>

我们将其变成哪种迭代器?
source§

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

从一个值创建一个迭代器。 Read more
source§

impl<T> IntoIterator for BinaryHeap<T>

source§

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}");
}
Run
§

type Item = T

被迭代的元素的类型。
§

type IntoIter = IntoIter<T>

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

Auto Trait Implementations§

§

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

§

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

§

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

§

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

§

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

Blanket Implementations§

source§

impl<T> Any for Twhere T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

获取 selfTypeIdRead more
source§

impl<T> Borrow<T> for Twhere T: ?Sized,

source§

fn borrow(&self) -> &T

从拥有的值中一成不变地借用。 Read more
source§

impl<T> BorrowMut<T> for Twhere T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

从拥有的值中借用。 Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

返回未更改的参数。

source§

impl<T, U> Into<U> for Twhere U: From<T>,

source§

fn into(self) -> U

调用 U::from(self)

也就是说,这种转换是 From<T> for U 实现选择执行的任何操作。

source§

impl<T> ToOwned for Twhere T: Clone,

§

type Owned = T

获得所有权后的结果类型。
source§

fn to_owned(&self) -> T

从借用的数据创建拥有的数据,通常是通过克隆。 Read more
source§

fn clone_into(&self, target: &mut T)

使用借来的数据来替换拥有的数据,通常是通过克隆。 Read more
source§

impl<T, U> TryFrom<U> for Twhere U: Into<T>,

§

type Error = Infallible

发生转换错误时返回的类型。
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

执行转换。
source§

impl<T, U> TryInto<U> for Twhere U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

发生转换错误时返回的类型。
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

执行转换。