How does the following comparator even works while building up the min heap?

Question

I know that if I build a heap using STL, it makes a max_heap. And if I want to make a min_heap, I will have to write my own custom comparator. Now, the following comparator,

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

The above code I got from off of the internet. I just have one doubt. How is the comparator actually working. And as far as I understand, shouldn't it be something like, return a < b because we want the minimum element to be in the front and then the bigger element in the heap. Why is it return a > b. Doesn't it mean that, if (a>b), then this will return true and a will be put in the heap before b and therefore a bigger element is put in front of a smaller element?

Answer 1

I think you're reading too much into a connection between the comparator semantics and the heap semantics. Remember, the internal details and structure of containers are deliberately abstracted away from you so, the moment you started trying to rationalise about this in terms of how you think the internal structure of a max_heap should look, you got carried away.

In the standard library, default comparators are always less-than. If the relationship between elements for sorting within the particular container/algorithm is not less-than, the container/algorithm will be clever enough to make that transformation (in this case, on usual implementations, by simply passing the operands in the reverse order, like cmp(b,a)!). But, fundamentally, it will always start with a less-than ordering because that is the consistent convention adopted.

So, to invert the ordering of your container, you would take a less-than comparator and turn it into a greater-than comparator, no matter what the physical layout of the container's implementation may (in your opinion) turn out to be.

Furthermore, as an aside, and to echo the Croissant's comments, I would take longs by value … and, in fact, just use std::greater rather than recreating it.

Answer 2

Standard heap builds in such a way that for every element a and its child b, the comparison cmp(b,a) holds, where cmp is the comparator supplied. Note that the first argument to cmp is the child. (Or, abstracting from the internal representation, the standard way is so that cmp(top, other) is true for the first element top and any other other.)

This is obviously done to make the default comparator ("less") build max-heap.

So you need to provide a comparator which you want to return true when a child is supplied as a first argument. For the min-heap, this will be 'greater'.