Odtnhj

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.

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;

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

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;