bigywater.tech
Rust · 70

BinaryHeap 优先队列

BinaryHeap 是 Rust 里的优先队列。它的遍历顺序为什么不是排序的?相同优先级先进先出吗?批量建堆比逐个 push 省多少比较?这篇用计数的 Ord 把这些都量出来,最后用 Dijkstra 收尾。

堆序
into_vec 与 iter 的顺序只满足堆性质,不是排序
188028 对 228034
n=100000 时 from(vec) 对逐个 push 的比较次数
Reverse
把最大堆变成最小堆的包装类型

最大堆与内部数组

实测 · 本机执行输出
  编译:成功
  运行(退出码 0):
    peek = Some(9)  len = 7
    内部数组 into_vec(堆序,不是排序): [9, 8, 7, 1, 3, 2, 5]
    连续 pop: [9, 8, 7, 5, 3, 2, 1]
    into_sorted_vec(升序): [1, 2, 3, 5, 7, 8, 9]
    iter() 的顺序是内部数组顺序,不是排序: [9, 8, 7, 1, 3, 2, 5]
    最小堆(Reverse):连续 pop [1, 3, 5, 8]

相同优先级

实测 · 本机执行输出
  编译:成功
  运行(退出码 0):
    只按 pri 比较:   [(2, 1), (2, 5), (2, 3), (2, 7), (1, 6), (1, 2), (1, 4), (1, 0)]
    pri 相同再按 seq:[(2, 1), (2, 3), (2, 5), (2, 7), (1, 0), (1, 2), (1, 4), (1, 6)]

peek_mut

实测 · 本机执行输出
  编译:成功
  运行(退出码 0):
    初始 peek Some(10)
    把堆顶改成 0,此时 PeekMut 还没离开作用域
    离开作用域后 peek Some(8)(堆自动重排)
    PeekMut::pop 取出 8
    剩下按序: [0, 1, 7]

比较次数

实测 · 本机执行输出
  编译:成功
  运行(退出码 0):
           n        逐个 push      from(vec)         全部 pop  n·log2(n)
        1000           2185           1851           8684       9966
       10000          22731          18772         120101     132877
      100000         228034         188028        1534578    1660964

用静态计数器在 Ord::cmp 里累加得到;随机数据,release 构建;数字随数据略有波动。

Dijkstra

实测 · 本机执行输出
  编译:成功
  运行(退出码 0):
    从节点 0 出发的最短距离: [0, 7, 9, 20, 20, 11](堆总共 pop 了 8 次)

排序见sort 与 sort_unstable。

分步演示

BinaryHeap
本步的对象

    本文用到的工具与边界

    • 本机 macOS 27 arm64 / rustc 1.98.1(brew)/ cargo 1.98.1;单个文件用 rustc 直接编译,需要依赖时用 cargo(经代理从 crates.io 下载);计时用 std::time::Instant,数字每次运行会有小幅抖动
    • 没有验证:push 的最坏复杂度、into_sorted_vec 的比较次数、与 BTreeSet 作优先队列的速度对比、decrease-key(标准库没有这个操作)、append/merge 的复杂度
    京ICP备2026067502号-1京公网安备11010502063487号