有没有 C++最小最大堆实现?
我正在寻找类似于 stl 中的算法(push_heap
、pop_heap
、make_heap
),除了能够弹出最小值和最大值有效地实现价值。又称双端优先级队列。如此处所述。
作为替代方案,双端优先级队列的任何干净实现也将引起人们的兴趣,但是这个问题主要是关于 MinMax Heap 实现。
我的 google-fu 尚未取得成果,但它肯定存在吗?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(5)
您是否有无法使用
std::set
的原因?听起来,加上一些访问和删除set::begin()
和--set::end()
的包装器将解决问题。我想很难找到比 set 的默认实现更快地完成 MinMax Heap 的东西。Is there a reason you can't use
std::set
? It sounds like that, along with some wrappers to access and removeset::begin()
and--set::end()
will solve the problem. I imagine it will be difficult to find something that can generally do a MinMax Heap much faster than the default implementation of set.我找不到任何好的实现,但由于没有其他人可以,我猜您会编写自己的实现,在这种情况下,我为您提供了一些方便的参考。
一篇似乎没有人提到的论文是 Min-Max-Heaps 的原始命题:
http://www.cs.otago.ac.nz/staffpriv/mike/Papers/MinMaxHeaps/MinMaxHeaps.pdf
我已经从这篇论文中实现了两次最小-最大堆(不是 C 语言)并且发现它相当微不足道。
我从未实施过的一项改进是最小-最大-精细堆。我在普通的旧细堆上找不到任何好的论文或参考文献,但我确实在 min-max-fine-heap 上找到了一篇,它显然表现更好:
http://arxiv.org/ftp/cs/papers/0007/0007043.pdf
I can't find any good implementations, but since no one else can either I'm guessing you'll be writing your own, in which case I have a few handy references for you.
A paper that no one seems to have mentioned is the original proposition for Min-Max-Heaps:
http://www.cs.otago.ac.nz/staffpriv/mike/Papers/MinMaxHeaps/MinMaxHeaps.pdf
I've implemented a min-max heap from this paper twice (not in C) and found it fairly trivial.
An improvement, which I haven't ever implemented, is a Min-Max-Fine-Heap. I can't find any good papers or references on a plain old fine heap, but I did find one on the min-max-fine-heap, which apparently performs better:
http://arxiv.org/ftp/cs/papers/0007/0007043.pdf
如果您正在寻找算法实现,请尝试搜索 Github 。
If you're looking for the algorithm implementation try searching Github.
不确定这是否正是您正在寻找的,但这是我在大学时代创建的 MinMax 堆。这是一个更大项目的一部分,因此,在测量性能的“秒表”类上有一个无关的参考。我不包括这门课,因为这不是我的工作。删除它并不难,所以我保留对它的引用不变。
snipplr 上的代码
要使用,只需使用任何内容创建一个新的堆实例您要使用的类型。 (注意,自定义类型需要重载比较运算符)。创建该类型的数组,然后将其传递给构造函数并指定当前数组大小和最大值。此实现仅在传递的数组之上工作,因为这是我唯一需要的东西,但您拥有实现推送和弹出方法所需的一切。
Not sure if this is exactly what you're looking for, but here is a MinMax Heap i created back in my university days. This was part of a larger project so, there is an extraneous reference on a 'Stopwatch' class which measured performance. I'm not including this class as it isn't my work. It isn't hard to strip it out so i'm leaving the reference to it as it is.
The code on snipplr
To use, just create a new instance of the heap with whatever type you want to use. (Note, custom types would need to overload comparison operators). Create array of that type and then pass it to the constructor and specify the current array size and what the maximum should be. This implementation works on top of a passed array only since this is the only thing i needed, but you have everything you need to implement push and pop methods.
抱歉,代码很长,但它工作正常,只是它可能会使阅读变得复杂,并且可能包含一些不必要的变量,而且我没有上传插入函数。将其用作包含 .h
文件。
Sorry for lengthy code but it works fine except it may complicate to read and may contain some unnecessary variables and I am not uploading the Insert function. Use it as include .h
file.