Компаратор для минимальной кучи в C++

Я пытаюсь сделать min-heap1 из longs в 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. Теперь я думаю, что мой компаратор определенно не работает, но не знаю, почему.

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


c++ stl comparator heap min-heap
person Jakob Weisblat    schedule 24.12.2012    source источник
comment
вы используете тот же компаратор для make_heap?   -  person perreal    schedule 24.12.2012
comment
Я использую тот же компаратор для make_heap, но только что понял, что могу не использовать его для sort_heap.   -  person Jakob Weisblat    schedule 24.12.2012
comment
@perreal Я хочу создать min-heap, но STL делает max-heap, если я не передам ему компаратор.   -  person Jakob Weisblat    schedule 24.12.2012
comment
что вы подразумеваете под рабочим примером кода?   -  person Jakob Weisblat    schedule 24.12.2012
comment
Простите меня, если я не прав, я мало работаю в C/C++, но разве const long& a и const long& b не указывают указатели на константные значения, и поэтому сравнение a с b является сравнением адресов этих значений?   -  person Zéychin    schedule 24.12.2012
comment
@Zéychin, который передается по ссылке. Они автоматически разыменовываются. a * сделал бы его указателем.   -  person Jakob Weisblat    schedule 24.12.2012
comment
О да. Это верно. Не обращай внимания на мою глупость.   -  person Zéychin    schedule 24.12.2012

Ответы (3)


arrow_upward
21
arrow_downward

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

#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;
}
person perreal    schedule 24.12.2012
comment
по какой-то причине, после того, как я несколько раз вынул и прочитал ,greater1() на мои вызовы, теперь он работает. Возможно, он генерировал ошибки компилятора, которых я не заметил (у меня запущен скрипт g++ file.cpp;./a.out), и он, наконец, скомпилировался после того, как я удалил ошибку. Кто знает. В любом случае, поскольку вы помогли решить мою проблему, я принимаю это. - person Jakob Weisblat; 24.12.2012
comment
спасибо, также, возможно, вы имеете в виду std::push_heap(humble.begin(),humble.end(),greater1()); внутри блока if. - person perreal; 24.12.2012
comment
Я хочу, чтобы это было там. Хороший улов. Объясняет мои ошибки для гораздо больших значений, но не мою самую новую ошибку (Недопустимое открытие файла (/dev/tty)) - person Jakob Weisblat; 24.12.2012
comment
g++ файл.cpp && ./a.out - person Joshua; 01.08.2016

arrow_upward
16
arrow_downward

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

person zyfo2    schedule 25.07.2013

arrow_upward
1
arrow_downward

Вы хотите снова вызвать 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;
}
person Dobob    schedule 31.07.2016