具有用户定义类型的 C++ 最小堆 [英] C++ min heap with user-defined type

问题描述

我正在尝试在 C++ 中为我创建的结构类型实现最小堆.我创建了一个该类型的向量，但是当我在它上面使用 make_heap 时它崩溃了，这是可以理解的，因为它不知道如何比较堆中的项目.如何为结构类型创建最小堆(即，顶部元素始终是堆中最小的元素)?

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?

结构如下:

struct DOC{

int docid;
double rank;

};

我想使用等级成员比较 DOC 结构.我该怎么做?

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.

非常感谢，bsg

推荐答案

添加比较运算符:

struct DOC{

    int docid;
    double rank;
    bool operator<( const DOC & d ) const {
       return rank < d.rank;
    }
};

结构几乎总是有用的构造函数，所以我还要补充:

Structures can almost always usefully have a constructor, so I would also add:

DOC( int i, double r ) : docid(i), rank(r) {]

也到结构体.

这篇关于具有用户定义类型的 C++ 最小堆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！