Struct std::collections::BinaryHeap1.0.0[−][src]

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

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

这将是一个最大的堆。

以某种方式修改项目是一种逻辑错误，即该项目相对于任何其他项目的排序 (由 Ord trait 确定) 在堆中时会发生变化。

通常只有通过 Cell，RefCell，二进制状态，I/O 或不安全代码才能实现此操作。 未指定由此类逻辑错误导致的行为，但不会导致未定义的行为。 这可能包括 panics，不正确的结果，异常终止，内存泄漏和未终止。

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

Min-heap

std::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

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

Examples

基本用法:

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

创建具有特定容量的空 BinaryHeap。 这为 capacity 元素预分配了足够的内存，因此 BinaryHeap 至少包含这么多的值之前不必重新分配。

Examples

基本用法:

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

返回二进制堆中最大项的变量引用; 如果为空，则返回 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)。

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

Examples

基本用法:

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

时间复杂度

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

将项目推入二进制堆。

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)。最坏的情况发生在容量用尽并需要调整大小时。 调整大小成本已在之前的数字中摊销。

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

Examples

基本用法:

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

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

Examples

基本用法:

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());
Run
🔬 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(vec![1, 2, 3, 4, 5]);
assert_eq!(heap.len(), 5);

drop(heap.drain_sorted()); // 删除堆顺序中的所有元素
assert_eq!(heap.len(), 0);
Run
🔬 This is a nightly-only experimental API. (binary_heap_retain #71503)

仅保留谓词指定的元素。

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

Examples

基本用法:

#![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); // 只保留偶数

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

返回以任意顺序访问基础 vector 中的所有值的迭代器。

Examples

基本用法:

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

// 以任意顺序打印 1，2，3，4
for x in heap.iter() {
    println!("{}", x);
}
Run
🔬 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(vec![1, 2, 3, 4, 5]);

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

返回二进制堆中最大的项，如果为空，则返回 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)。

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

Examples

基本用法:

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

保留最小容量，以便在给定的 BinaryHeap 中精确插入 additional 个元素。 如果容量已经足够，则不执行任何操作。

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

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

保留至少 additional 个要插入 BinaryHeap 中的更多元素的容量。 该集合可以保留更多空间，以避免频繁的重新分配。

Panics

如果新容量溢出 usize，则为 Panics。

Examples

基本用法:

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

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

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
🔬 This is a nightly-only experimental API. (shrink_to #56431)

new API

丢弃容量下限。

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

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

Examples

#![feature(shrink_to)]
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
🔬 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(vec![1, 2, 3, 4, 5, 6, 7]);

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

消耗 BinaryHeap 并以任意顺序返回基础 vector。

Examples

基本用法:

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

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

返回二进制堆的长度。

Examples

基本用法:

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

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

检查二进制堆是否为空。

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

清除二进制堆，并在删除的元素上返回一个迭代器。

元素以任意顺序删除。

Examples

基本用法:

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

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

Examples

基本用法:

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

assert!(!heap.is_empty());

heap.clear();

assert!(heap.is_empty());
Run

Trait Implementations

返回值的副本。 Read more

从 source 执行复制分配。 Read more

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

创建一个空的 BinaryHeap<T>。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Examples

基本用法:

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

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

被迭代的元素的类型。

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

被迭代的元素的类型。

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

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

Auto Trait Implementations

Blanket Implementations

获取 self 的 TypeId。 Read more

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

从拥有的值中借用。 Read more

执行转换。

执行转换。

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

通常通过克隆从借用数据中创建拥有的数据。 Read more

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

recently added

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

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

执行转换。

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

执行转换。