是否有C++ MinMax Heap实现？

Question

我正在寻找像stl(push_heap,, )中的算法pop_heap,make_heap除了能够有效地弹出最小值和最大值.AKA双端优先级队列.如上所述这里.

作为替代方案,双端优先级队列的任何干净实现也是有意义的,但是这个问题主要是关于MinMax Heap实现.

我的google-fu并不富有成效,但当然,它必须存在？

Answer 1

有没有理由你不能使用std::set？听起来像这样,以及一些包装器来访问和删除set::begin(),--set::end()并将解决问题.我想很难找到通常可以比默认的set实现快得多的MinMax Heap的东西.

@Slauma还有`std :: multiset`. (3认同)
但是对于大堆/大量操作,集合实现将比minimax堆慢... ... minimax堆具有与普通堆相同的时间复杂度,即具有O(1)find-min/find-max操作,而对于通用集实现find-min和find-max通常为O(log n). (3认同)
我已经对 antti.huimas 评论投了赞成票，但这可能是过早的优化。也许可以抽象队列，以便在真正需要时可以换出实现。或者不要 - 如果需要，重构以换出它可能无论如何都不会太多。另外，我相信在 std::set 中找到端点实际上是 O(1) - set 对象实际上包含指向最小和最大节点以及根的指针，因此 begin() 和 end( ) 得到有效处理。 (2认同)

Answer 2

如果您正在寻找算法实现，请尝试搜索Github。