Компаратор для мини-кучи в С++

Я пытаюсь сделать min-heap ¹ of long в С++ с использованием 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 popped.

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

EDIT:
Я понял, что я запускаю sort_heap без компаратора, тогда как когда я запускаю этот компаратор, я получаю [15,15,9,25] от sort_heap. Теперь я думаю, что мой компаратор определенно не работает, но не знаю почему.

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

Ответ 1

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

#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;
}

Ответ 2

просто используйте больше '<' int > (). он предопределен.

Ответ 3

Вы хотите снова называть make_heap на векторе, а не sort_heap. make_heap перегруппирует весь ваш вектор в кучу min, учитывая большее, чем компаратор, тогда как 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;
}