для определяемой пользователем структуры, как я понимаю, легко. Просто перегрузите оператор <. Однако для 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 должно сделать трюк. Однако, что вы имеете в виду, я не должен использовать внешний компаратор? Если это не так, какой общий способ достичь этого?
Вам не нужно перегружать operator < для int (вы не можете, фактически). Если вы используете внешний компаратор, вы должны передавать те же Comparator comp в pop_head.
* Изменить: *
Как указывал ildjarn, ваш оператор сравнения не выполняет строго строго-упорядоченное отношение.
a < b ? false : true; --> a >= b
b < a ? true : false; --> a > b
Используйте 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 становится a max heap. Чтобы иметь min heap, с другой стороны, вам нужно добавить компаратор, но не нужно его реализовывать. Вместо этого вызовите метод следующим образом:
make_heap(A.begin(), A.end(), greater<int>());
Этот вызов сделает ваш массив a min heap.
PS: #include <algorithm> необходимо использовать std::make_heap.
Те же операции применяются и к vector.
НТН!