Comparator for min-heap in C++

Question

I am trying to make a min-heap¹ of longs in C++ using the STL make_heap, etc., but my comparator doesn't seem to be comparing properly. The following is my current comparator:

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

However, when I do std::pop_heap(humble.begin(),humble.end(),g); where g is an instance of greater1 and humble is a heap who makes [9,15,15,25] when sort_heap is called, I get a 15 popped.

Is my comparator correct? what might be going wrong?

EDIT:
I realized that I am running sort_heap with no comparator, whereas when I run it this comparator, I get [15,15,9,25] from sort_heap. Now I am thinking my comparator is definitely not working, but unsure why.

¹The STL makes a max-heap by default, so I need a comparator.

I use the same comparator for `make_heap` but just realized I might not be using it for `sort_heap`. — Jakob Weisblat, Dec 24 '12 at 04:08
@perreal I want to make a **min-heap** but the STL does a max-heap if I pass it no comparator. — Jakob Weisblat, Dec 24 '12 at 04:16
Pardon me if I'm incorrect here, I don't work in C/C++ much, but don't `const long& a` and `const long& b` indicate pointers to constant values, and therefore comparing `a` to `b` is comparing the addresses of these values? — Zéychin, Dec 24 '12 at 04:24
@Zéychin that is passing by reference. They are automatically dereferenced. a \* would make it a pointer. — Jakob Weisblat, Dec 24 '12 at 04:26

score 22 · Accepted Answer · answered Dec 24 '12 at 04:28

22

Perhaps you are missing something somewhere, the code below works as intended:

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

answered Dec 24 '12 at 04:28

perreal

94,503
21
155
181

for some reason, after taking out and readding ",greater1()" to my calls a few times, it now works. Maybe it was generating compiler errors that I didn't notice (I have a script run `g++ file.cpp;./a.out`) and it finally compiled after I removed an error. Who knows. Anyway, since you were helpful to solving my problem, I'm accepting this. – Jakob Weisblat Dec 24 '12 at 04:41
thanks, also maybe you mean to have the `std::push_heap(humble.begin(),humble.end(),greater1());` inside the if block. – perreal Dec 24 '12 at 04:47
I do mean to have that there. Good catch. Explains my errors for much larger values but not my newest error ( "Illegal file open (/dev/tty)") – Jakob Weisblat Dec 24 '12 at 04:49
1

g++ file.cpp && ./a.out – Joshua Jul 31 '16 at 23:42

score 17 · Answer 2 · edited Nov 11 '18 at 07:19

17

just use greater<int>(). it is predefined in std.

edited Nov 11 '18 at 07:19

Daniel Heilper

1,182
2
17
34

answered Jul 25 '13 at 07:39

zyfo2

302
2
6

Dobob · Answer 3 · 2016-08-01T00:41:50.913

You want to call make_heap on the vector again, not sort_heap. make_heap will rearrange your entire vector into a min heap given the greater-than comparator whereas sort_heap sorts your element into ascending order and is no longer a heap at all!

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

Comparator for min-heap in C++

3 Answers3

Linked