Блог

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

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

       bool comp(const intamp; a, const intamp; 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 в pop_heap или push_heap должна помочь. Однако, что вы имеете в виду, я не должен использовать внешний компаратор? Если это неправильный способ, каков общий способ добиться этого?

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

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

 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 становится max heap . min heap С другой стороны, чтобы иметь a, вам нужно добавить компаратор, но не нужно его реализовывать. Вместо этого вызовите метод следующим образом:

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

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

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

HTH!

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

* Редактировать: *

Как указал ильджарн, ваш оператор сравнения не реализует отношение строгого слабого порядка.

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