Struct std::collections::BinaryHeap 1.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())可以从数组初始化具有已知项列表的 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 的值是预期成本； 方法文档提供了更详细的分析。
Implementations
返回二进制堆中最大项的变量引用; 如果为空，则返回 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)。
将项目推入二进制堆。
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)。最坏的情况发生在容量用尽并需要调整大小时。
调整大小成本已在之前的数字中摊销。
将 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());pub fn drain_sorted(&mut self) -> DrainSorted<'_, T>ⓘNotable traits for DrainSorted<'_, T>impl<'_, T> Iterator for DrainSorted<'_, T> where
T: Ord, type Item = T;
pub fn drain_sorted(&mut self) -> DrainSorted<'_, T>ⓘNotable traits for DrainSorted<'_, T>impl<'_, T> Iterator for DrainSorted<'_, T> where
T: Ord, type Item = T;
impl<'_, T> Iterator for DrainSorted<'_, T> where
T: Ord, type Item = T;返回一个迭代器，该迭代器以堆顺序检索元素。 检索到的元素将从原始堆中删除。 其余元素将按堆顺序丢弃。
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);pub fn into_iter_sorted(self) -> IntoIterSorted<T>ⓘNotable traits for IntoIterSorted<T>impl<T> Iterator for IntoIterSorted<T> where
T: Ord, type Item = T;
pub fn into_iter_sorted(self) -> IntoIterSorted<T>ⓘNotable traits for IntoIterSorted<T>impl<T> Iterator for IntoIterSorted<T> where
T: Ord, type Item = T;
impl<T> Iterator for IntoIterSorted<T> where
T: Ord, type Item = T;保留最小容量，以便在给定的 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);尝试为要插入给定 BinaryHeap<T> 的 additional 元素保留最小容量。
调用 try_reserve_exact 后，如果返回 Ok(())，则容量将大于或等于 self.len() + additional。
如果容量已经足够，则不执行任何操作。
请注意，分配器可能会给集合提供比其请求更多的空间。
因此，不能依靠容量来精确地最小化。
如果希望将来插入，则首选 try_reserve。
Errors
如果容量溢出，或者分配器报告失败，则返回错误。
Examples
#![feature(try_reserve_2)]
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())
}尝试为至少 additional 更多的元素保留容量，以插入给定的 BinaryHeap<T> 中。
该集合可以保留更多空间，以避免频繁的重新分配。
调用 try_reserve 后，容量将大于或等于 self.len() + additional。
如果容量已经足够，则不执行任何操作。
Errors
如果容量溢出，或者分配器报告失败，则返回错误。
Examples
#![feature(try_reserve_2)]
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())
}Trait Implementations
创建一个空的 BinaryHeap<T>。
将 Vec<T> 转换为 BinaryHeap<T>。
此转换发生在原地，并且具有 O(n) 时间复杂度。
从迭代器创建一个值。 Read more
type Item = T
type Item = T
被迭代的元素的类型。