простой способ поддерживать минимальную кучу с STL? - PullRequest
Новая
       21

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

18 голосов
/ 07 октября 2011

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

       #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 не будет правильно поддерживать min-heap? Есть ли более простой способ добиться этого? Спасибо!

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

Ответы [ 3 ]

28 голосов
/ 07 октября 2011

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

15 голосов
/ 03 июля 2016

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

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

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

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

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

НТН!

8 голосов
/ 07 октября 2011

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

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

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

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