可寻址配对堆

Rust 的可寻址配对堆实现。

允许高效地存储与键相关联的元素并通过句柄访问它们。元素句柄使得能够查询和编辑存储在 PairingHeap 中的元素。

文档: 链接
crates.io: 链接

基准测试显示当前实现存在性能问题，尚未解决

二叉堆

test bench::binary_heap_clone        ... bench:      27,409 ns/iter (+/- 1,958)
test bench::binary_heap_pop          ... bench:   3,227,855 ns/iter (+/- 35,525)
test bench::binary_heap_pop_bigpod   ... bench:  17,386,429 ns/iter (+/- 85,175)
test bench::binary_heap_push         ... bench:   1,522,285 ns/iter (+/- 39,222)
test bench::binary_heap_push_bigpod  ... bench:  10,600,908 ns/iter (+/- 226,227)

配对堆

test bench::pairing_heap_clone       ... bench:   1,713,716 ns/iter (+/- 43,337)
test bench::pairing_heap_pop         ... bench:  11,255,949 ns/iter (+/- 209,302)
test bench::pairing_heap_pop_bigpod  ... bench:  26,683,916 ns/iter (+/- 136,507)
test bench::pairing_heap_push        ... bench:   2,644,503 ns/iter (+/- 34,863)
test bench::pairing_heap_push_bigpod ... bench:  10,997,608 ns/iter (+/- 161,914)