logo - Comparador para min-heap en C++

hbase

Question

Estoy tratando de hacer un min-heap ¹ de long s en C ++ usando STL make_heap , etc., pero mi comparador no parece estar comparando correctamente. El siguiente es mi comparador actual:

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

Sin embargo, cuando hago std::pop_heap(humble.begin(),humble.end(),g); donde g es una instancia de greater1 y humble es un montón que hace [9,15,15,25] cuando se llama sort_heap , obtengo un 15 pop.

¿Mi comparador es correcto? ¿Qué podría estar yendo mal?

EDITAR:
Me di cuenta de que estoy ejecutando sort_heap sin comparador, mientras que cuando lo ejecuto, obtengo [15,15,9,25] de sort_heap . Ahora estoy pensando que mi comparador definitivamente no funciona, pero no estoy seguro de por qué.

¹ El STL crea un max-heap por defecto, así que necesito un comparador.

Answer 1

Quieres llamar a make_heap en el vector de nuevo, no sort_heap . make_heap reorganizará todo tu vector en un montón mínimo dado el comparador mayor que el orden_heap ordena tu elemento en orden ascendente y ya no es un montón en absoluto!

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

Answer 2

Tal vez le falta algo en algún lugar, el siguiente código funciona según lo previsto:

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

Answer 3

solo usa greater<int>() . Está predefinido en estándar.