Struct alloc::collections::binary_heap::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]);
RunMin-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时间复杂度
push
的值是预期成本; 方法文档提供了更详细的分析。
Implementations§
source§impl<T: Ord> BinaryHeap<T>
impl<T: Ord> BinaryHeap<T>
sourcepub fn new() -> BinaryHeap<T>
pub fn new() -> BinaryHeap<T>
sourcepub fn with_capacity(capacity: usize) -> BinaryHeap<T>
pub fn with_capacity(capacity: usize) -> BinaryHeap<T>
1.12.0 · sourcepub fn peek_mut(&mut self) -> Option<PeekMut<'_, T>>
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)。
sourcepub fn push(&mut self, item: T)
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 · sourcepub fn into_sorted_vec(self) -> Vec<T>
pub fn into_sorted_vec(self) -> Vec<T>
sourcepub fn drain_sorted(&mut self) -> DrainSorted<'_, T> ⓘ
🔬This is a nightly-only experimental API. (binary_heap_drain_sorted
#59278)
pub fn drain_sorted(&mut self) -> DrainSorted<'_, T> ⓘ
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);
Runsource§impl<T> BinaryHeap<T>
impl<T> BinaryHeap<T>
sourcepub fn into_iter_sorted(self) -> IntoIterSorted<T> ⓘ
🔬This is a nightly-only experimental API. (binary_heap_into_iter_sorted
#59278)
pub fn into_iter_sorted(self) -> IntoIterSorted<T> ⓘ
binary_heap_into_iter_sorted
#59278)sourcepub fn reserve_exact(&mut self, additional: usize)
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);
Runsourcepub fn reserve(&mut self, additional: usize)
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);
Run1.63.0 · sourcepub fn try_reserve_exact(
&mut self,
additional: usize
) -> Result<(), TryReserveError>
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())
}
Run1.63.0 · sourcepub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError>
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())
}
Runsourcepub fn shrink_to_fit(&mut self)
pub fn shrink_to_fit(&mut self)
sourcepub fn as_slice(&self) -> &[T]
🔬This is a nightly-only experimental API. (binary_heap_as_slice
#83659)
pub fn as_slice(&self) -> &[T]
binary_heap_as_slice
#83659)Trait Implementations§
source§impl<T: Clone> Clone for BinaryHeap<T>
impl<T: Clone> Clone for BinaryHeap<T>
1.4.0 · source§impl<T: Debug> Debug for BinaryHeap<T>
impl<T: Debug> Debug for BinaryHeap<T>
source§impl<T: Ord> Default for BinaryHeap<T>
impl<T: Ord> Default for BinaryHeap<T>
source§fn default() -> BinaryHeap<T>
fn default() -> BinaryHeap<T>
创建一个空的 BinaryHeap<T>
。
1.2.0 · source§impl<'a, T: 'a + Ord + Copy> Extend<&'a T> for BinaryHeap<T>
impl<'a, T: 'a + Ord + Copy> Extend<&'a T> for BinaryHeap<T>
source§fn extend_one(&mut self, item: &'a T)
fn extend_one(&mut self, item: &'a T)
extend_one
#72631)source§impl<T: Ord> Extend<T> for BinaryHeap<T>
impl<T: Ord> Extend<T> for BinaryHeap<T>
source§fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)
fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)
source§fn extend_one(&mut self, item: T)
fn extend_one(&mut self, item: T)
extend_one
#72631)1.5.0 · source§impl<T> From<BinaryHeap<T>> for Vec<T>
impl<T> From<BinaryHeap<T>> for Vec<T>
source§fn from(heap: BinaryHeap<T>) -> Vec<T>
fn from(heap: BinaryHeap<T>) -> Vec<T>
将 BinaryHeap<T>
转换为 Vec<T>
。
这种转换不需要数据移动或分配,并且具有恒定的时间复杂度。
1.5.0 · source§impl<T: Ord> From<Vec<T, Global>> for BinaryHeap<T>
impl<T: Ord> From<Vec<T, Global>> for BinaryHeap<T>
source§fn from(vec: Vec<T>) -> BinaryHeap<T>
fn from(vec: Vec<T>) -> BinaryHeap<T>
将 Vec<T>
转换为 BinaryHeap<T>
。
此转换发生在原地,并且具有 O(n) 时间复杂度。