C++ min heap с пользовательским типом

Я пытаюсь реализовать кучу минут в C++ для типа структуры, который я создал. Я создал вектор типа, но он разбился, когда я использовал make_heap на нем, что понятно, потому что он не знает, как сравнивать элементы в куче. Как создать мини-кучу (то есть, верхний элемент всегда самый маленький в куче) для типа структуры?C++ min heap с пользовательским типом

структура ниже:

struct DOC{ 

int docid; 
double rank; 

};

Я хочу, чтобы сравнить DOC структуры с использованием элемента ранга. Как мне это сделать?

Я попытался использовать очередь приоритетов со классом-компаратором, но это также разбилось, и также кажется глупым использовать структуру данных, которая использует кучу в качестве ее базовой основы, когда мне действительно нужна куча в любом случае.

Большое спасибо, BSG

источник

2010-04-04 bsg

Какое у вас определение «он разбился»? Разумеется, если у вас нет функции сравнения или оператора sellibitze

Нет, на самом деле я этого не делал. Определенно не с приоритетной очередью, в которой был задан перегруженный оператор, и я тоже не думаю с помощью make_heap. Хотя это может быть так, что в последнем случае я получил ошибку компиляции. В первый раз, однако, он скомпилировался отлично, но разбился во время выполнения. – bsg

Если вы попытаетесь использовать make_heap только с двумя аргументами, вам нужно иметь оператор <для вашего типа структуры. Если вы этого не сделаете, вы получите ошибки компиляции. Просто как тот. – sellibitze

Добавить оператор сравнения:

struct DOC{ 

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

структуры почти всегда полезно иметь конструктор, поэтому я хотел бы добавить:

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

в структура также.

источник

2010-04-04 09:46:20

Насколько я могу судить, это приведет к «максимальной куче». Но он хочет «кучу минут», которая требует функтора, который возвращает true тогда и только тогда, когда первый аргумент больше второго. – sellibitze

Большое спасибо! Я закончил использование очереди приоритетов, потому что у нее было больше функций, которые мне нужны, но я создал конструктор и перегрузил операторы < and >, как вы показали, и это сработало! – bsg

@bsg, если «это сработало», вы задали неправильный вопрос, и «максимальная куча» - это то, что вы хотели. Прими решение. – sellibitze

Просто создайте свой собственный «функтор» для сравнения. Так как вы хотите «мин кучи» Ваша функция сравнения должна вести себя как большую, чем оператор:

#include <iostream> 
#include <vector> 
#include <algorithm> 

struct doc { 
    double rank; 
    explicit doc(double r) : rank(r) {} 
}; 

struct doc_rank_greater_than { 
    bool operator()(doc const& a, doc const& b) const { 
     return a.rank > b.rank; 
    } 
}; 

int main() { 
    std::vector<doc> docvec; 
    docvec.push_back(doc(4)); 
    docvec.push_back(doc(3)); 
    docvec.push_back(doc(2)); 
    docvec.push_back(doc(1)); 
    std::make_heap(docvec.begin(),docvec.end(),doc_rank_greater_than()); 
    std::cout << docvec.front().rank << '\n'; 
}

Очень важно, чтобы вы всегда использовать ту же функцию сравнения в дальнейших операциях кучи.

источник

2010-04-04 10:08:28 sellibitze

C++ min heap с пользовательским типом

ответ

Смежные вопросы