BinaryHeap 是 Rust 里的优先队列。它的遍历顺序为什么不是排序的?相同优先级先进先出吗?批量建堆比逐个 push 省多少比较?这篇用计数的 Ord 把这些都量出来,最后用 Dijkstra 收尾。
编译:成功
运行(退出码 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)] 编译:成功
运行(退出码 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 构建;数字随数据略有波动。
编译:成功
运行(退出码 0):
从节点 0 出发的最短距离: [0, 7, 9, 20, 20, 11](堆总共 pop 了 8 次)