stl — Компаратор для мини-кучи в переполнении стека

Question

stl — Компаратор для мини-кучи в переполнении стека

Я пытаюсь сделать мин-кучу¹ из longв C ++ с использованием STL make_heapи т. д., но мой компаратор, кажется, не сравнивает должным образом. Вот мой текущий компаратор:

struct greater1{
bool operator()(const long& a,const long& b) const{
return a>b;
}
};

Тем не менее, когда я делаю std::pop_heap(humble.begin(),humble.end(),g); где g это пример greater1 а также humble это куча, которая делает [9,15,15,25] когда sort_heap называется, я получаю 15 совал.

Мой компаратор правильный? что может быть не так?

РЕДАКТИРОВАТЬ:
Я понял, что я запускаю sort_heap без компаратора, тогда как при запуске этого компаратора я получаю [15,15,9,25] от sort_heap, Теперь я думаю, что мой компаратор определенно не работает, но не знаю почему.

¹STL делает max-heap по умолчанию, поэтому мне нужен компаратор.

20

c++comparator heap min-heap stl

Решение

Другие решения

просто используйте greater<int>(), это предопределено в стандарте.

8

Вы хотите позвонить make_heap опять на векторе, не sort_heap. make_heap будет переставлять весь ваш вектор в кучу мин, учитывая, что компаратор больше, чем sort_heap сортирует ваш элемент в порядке возрастания и больше не является кучей!

#include <algorithm>
#include <iostream>
#include <vector>

struct greater1{
bool operator()(const long& a,const long& b) const{
return a>b;
}
};

int main()
{
unsigned int myints[] = {10,20,30,5,15};
vector<unsigned int> v(myints, myints+5);

//creates max heap
std::make_heap(v.begin(). v.end()); // 30 20 10 5 15

//converts to min heap
std::make_heap(v.begin(). v.end(), greater1()); // 5 15 10 20 30

unsigned int s =  v.size();

//ALSO NEED TO PASS greater1() to pop()!!!
for(unsigned int i = 0; i < s; i++)
std::pop_heap(v.begin(). v.end(), greater1()); // popping order: 5 10 15 20 30

return 0;
}

1

Источник

Accepted Answer

Возможно, вы что-то упустили, код ниже работает так, как задумано:

#include <vector>
#include <algorithm>
#include <iostream>

struct greater1{
bool operator()(const long& a,const long& b) const{
return a>b;
}
};

int main() {
std::vector<long> humble;
humble.push_back(15);
humble.push_back(15);
humble.push_back(9);
humble.push_back(25);

std::make_heap(humble.begin(), humble.end(), greater1());
while (humble.size()) {
std::pop_heap(humble.begin(),humble.end(),greater1());
long min = humble.back();
humble.pop_back();
std::cout << min << std::endl;
}

return 0;
}

17