Простой способ поддерживать минимальную кучу с помощью stl?

для определяемой пользователем структуры, как я понимаю, легко. Просто перегрузите оператор <. Однако для int/float и т.д. Мне действительно нужно перегрузить оператор < для int? Вот что я пробовал:

       #include <iostream>
       #include <algorithm>
       #include <vector>
       using namespace std;

       bool comp(const int& a, const int& b)
       {
          return a<b?false:true;
       }

       int main () 
       {
         int myints[] = {10,20,30,5,15};
         vector<int> v(myints,myints+5);
         vector<int>::iterator it;
         make_heap(v.begin(), v.end(), comp);
         cout << "initial min heap   : " << v.front() << endl;
         for (unsigned i=0; i<v.size(); i++) cout << " " << v[i];
         cout<<endl;

         pop_heap (v.begin(),v.end());
         v.pop_back();
         for (unsigned i=0; i<v.size(); i++) cout << " " << v[i];
         cout<<endl;
       }

результаты:

        initial min heap   : 5
        5 10 30 20 15
        30 10 15 20

теперь pop_heap, push_heap не будет поддерживать мини-кучу правильно? есть ли более простой способ достичь этого? Спасибо!

Изменить: извините, я не проверял руководство внимательно. да, прохождение comp to pop_heap или push_heap должно сделать трюк. Однако, что вы имеете в виду, я не должен использовать внешний компаратор? Если это не так, какой общий способ достичь этого?

Ответ 1

Вам не нужно перегружать operator < для int (вы не можете, фактически). Если вы используете внешний компаратор, вы должны передавать те же Comparator comp в pop_head.

* Изменить: *

Как указывал ildjarn, ваш оператор сравнения не выполняет строго строго-упорядоченное отношение.

a < b ? false : true; --> a >= b
b < a ? true : false; --> a > b

Ответ 2

Используйте std::greater<int>() как компаратор (ко всем make_heap, push_heap, pop_heap). Важно отметить, что () - std::greater<int> - класс функтора, а не функция, поэтому вам нужен экземпляр.

Ответ 3

Ответы хорошие, поэтому я просто хотел добавить небольшой пример. Скажем, у вас есть следующий массив:

array<int, 10> A{5,2,8,3,4,1,9,12,0,7};

и вы хотите создать min heap. Самый быстрый способ сделать это - использовать алгоритм make_heap. Тем не менее, по умолчанию создается max heap. Другими словами, если вы вызываете:

make_heap(A.begin(), A.end());

A становится a max heap. Чтобы иметь min heap, с другой стороны, вам нужно добавить компаратор, но не нужно его реализовывать. Вместо этого вызовите метод следующим образом:

make_heap(A.begin(), A.end(), greater<int>());

Этот вызов сделает ваш массив a min heap.

PS: #include <algorithm> необходимо использовать std::make_heap. Те же операции применяются и к vector.

НТН!