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


c++ stl heap min-heap
person user268451    schedule 06.10.2011    source источник

Ответы (3)


arrow_upward
9
arrow_downward

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

* Изменить: *

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

a < b ? false : true; --> a >= b
b < a ? true : false; --> a > b
person K-ballo    schedule 07.10.2011
comment
Более серьезная проблема заключается в том, что его компаратор эквивалентен компаратору int operator>=, который не является компаратором строгого слабого порядка и, следовательно, незаконен. - person ildjarn; 07.10.2011
comment
извините, я не внимательно прочитал руководство. да, передача comp в pop_heap или push_heap должна помочь. Однако что вы имеете в виду, я не должен использовать внешний компаратор? Если это не правильный путь, каков общий способ добиться этого? - person user268451; 07.10.2011
comment
@ user268451: вы можете использовать внешний компаратор, если хотите, но он должен реализовывать отношение строгого-слабого порядка, поэтому логика, эквивалентная operator>=, не разрешена, но логика, эквивалентная operator< или operator>, разрешена. Для получения дополнительной информации см. эту прекрасную статью, автором которой является один из отцов современного C++: Заказать я говорю! - person ildjarn; 07.10.2011
comment
@ user268451: Возможно, я ошибся, но разве operator< по умолчанию не дает вам желаемый порядок? - person K-ballo; 07.10.2011
comment
@ K-ballo: оператор по умолчанию ‹ дает вам max-heap, max int вверху; Я хочу мин кучи, мин int сверху; поэтому я думаю, что вы имеете в виду, что правильный компаратор для моего случая: return a›=b?true:false; - person user268451; 07.10.2011
comment
@ user268451: Нет, с = в нем нет строгого порядка, я думаю, вам нужно b < a. - person K-ballo; 07.10.2011
comment
@user268451 user268451: Вы должны просто полностью избавиться от своего пользовательского компаратора и вместо этого использовать std::greater<int>(). - person ildjarn; 07.10.2011
comment
@ildjarn: Вам действительно следует представить всю информацию, которую вы дали, в виде полного ответа, это, безусловно, будет лучше, чем у меня. - person K-ballo; 07.10.2011
comment
@K-ballo: Ваш ответ включает комментарии, так что ваш ответ хорош, ИМО. :-] - person ildjarn; 07.10.2011
comment
@ildjarn: спасибо за ссылку на статью и все ваши комментарии. Я все еще новичок в stl, и эта статья кажется мне очень сложной для понимания. - person user268451; 07.10.2011
comment
@K-ballo: не могли бы вы дать полное и правильное определение функции bool comp в своем ответе? Я до сих пор не понимаю, зачем возвращать a‹b?false:true; не работает, но правильно b‹a?true:false. - person user268451; 07.10.2011
comment
@ user268451: допустим a == b. Тогда a<b?false:true верно. Это неправильно, компаратор требует, чтобы 25.3/4 С++ 03 имел свойство !comp(x,x) для всех x. Однако b<a?true:false ложно, так что все в порядке. - person Steve Jessop; 07.10.2011

arrow_upward
31
arrow_downward

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

person Steve Jessop    schedule 07.10.2011

arrow_upward
21
arrow_downward

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

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.

ХТХ!

person erol yeniaras    schedule 03.07.2016