Search code examples
c++stlheapcomparatormin-heap

Comparator for min-heap in C++


I am trying to make a min-heap1 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.

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


Solution

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