C++用户定义类型的最小堆
我正在尝试在 C++ 中为我创建的结构类型实现最小堆。我创建了该类型的向量,但是当我在其上使用 make_heap 时它崩溃了,这是可以理解的,因为它不知道如何比较堆中的项目。如何为结构类型创建最小堆(即顶部元素始终是堆中最小的元素)?
结构如下:
struct DOC{
int docid;
double rank;
};
我想使用排名成员来比较 DOC 结构。我该怎么做?
我尝试使用带有比较器类的优先级队列,但这也崩溃了,而且当我真正需要的是堆时,使用使用堆作为其底层基础的数据结构似乎也很愚蠢。
非常感谢, BSG
I am trying to implement a min heap in c++ for a struct type that I created. I created a vector of the type, but it crashed when I used make_heap on it, which is understandable because it doesn't know how to compare the items in the heap. How do I create a min-heap (that is, the top element is always the smallest one in the heap) for a struct type?
The struct is below:
struct DOC{
int docid;
double rank;
};
I want to compare the DOC structures using the rank member. How would I do this?
I tried using a priority queue with a comparator class, but that also crashed, and it also seems silly to use a data structure which uses a heap as its underlying basis when what I really need is a heap anyway.
Thank you very much,
bsg
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(2)
只需创建您自己的“函子”即可进行比较。由于您想要一个“最小堆”,您的比较函数的行为应该类似于大于运算符:
在进一步的堆操作中始终使用相同的比较函数非常重要。
Simply create your own "functor" for the comparison. Since you want a "min heap" your comparison function should behave like the greater than operator:
It's important that you always use the same comparison function in further heap operations.
添加比较运算符:
结构几乎总是可以有一个构造函数,所以我也会将:添加
到结构中。
Add a comparison operator:
Structures can almost always usefully have a constructor, so I would also add:
to the struct as well.