Creating Min Heap from STL Priority Queue

Question

I am creating a min heap from stl priority queue. Here is my class which I am using.

class Plane { private : int id ; int fuel ; public: Plane():id(0), fuel(0){} Plane(const int _id, const int _fuel):id(_id), fuel(_fuel) {} bool operator > (const Plane &obj) { return ( this->fuel > obj.fuel ? true : false ) ; }

} ;

In main I instantiate an object thus.

 priority_queue<Plane*, vector<Plane*>, Plane> pq1 ; pq1.push(new Plane(0, 0)) ;

I am getting an error from xutility which I am unable to understand.

d:\microsoft visual studio 10.0\vc\include\xutility(674): error C2064: term does not evaluate to a function taking 2 arguments

Any help to its solution would be appreciated.

Fred Foo · Accepted Answer · 2012-12-07 15:26:46Z

If you drop the use of pointers (which are overkill for your simple structures), then you can use std::greater from the header functional:

std::priority_queue<Plane, std::vector<Plane>, std::greater<Plane> > pq1; pq1.push(Plane(0, 0));

Currently, you are feeding Plane as the comparison type. That won't work since the comparison type must be a type of function object, i.e. it must have an operator() that does the comparison. Plane doesn't have such a member (and adding it just for this purpose would be a bad idea).

std::greater has the appropriate method, implemented in terms of your operator>. However, it doesn't work with pointers, because then it uses a pointer comparison (based on memory addresses).

Btw., note that your comparison function can be expressed more succinctly as

bool operator>(const Plane &other) { return fuel > other.fuel; }

Okay but for an upvote from me this answer needs an explanation of why the element type is an unsuitable comparator type and consequently why the OP's original code did not compile. :-)
It works fine, but I cannot get the reason behind that, as @Lightness Races in Orbit mentions.
@larsmans how would it know that it has to order according to my fuel?
std::greater will invoke your operator>. It just knows to do that.
@LightnessRacesinOrbit: too bad you didn't catch the gravest error of all: std::greater would do a pointer comparison. Changed the answer, again.

juanchopanza · Accepted Answer · 2012-12-07 15:38:30Z

7

The third template parameter must be a binary functor taking teo Plane*. Your Plane class does not provide that.

You need something of the form

struct CompPlanePtrs { bool operator()(const Plane* lhs, const Plane* rhs) const { return lhs->fuel > rhs->fuel ; } };

edited Dec 7, 2012 at 15:38

answered Dec 7, 2012 at 15:03

juanchopanza

228k35 gold badges421 silver badges493 bronze badges

2 Comments

Sasha Over a year ago

Can't i do that with operator >?. making it a friend? It doesnt get right with operator() either.

juanchopanza Over a year ago

@Sasha the problem is that you need to compare pointers to Planes, not Planes. You cannot overload operator> for pointers.

Collectives™ on Stack Overflow

Creating Min Heap from STL Priority Queue

2 Answers 2

7 Comments

2 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

7 Comments

2 Comments

Linked

Related