CODEWITHSUNDEEP
c++stlheap
etotientz
etotientz

Reputation: 414

Min Heap Custom Comparator in C++

I have a Point Class and am creating a min-heap of Point objects.

class Point
{
   int x;
   int y;
public:
   Point(int _x, int _y)
   {
      x = _x;
      y = _y;
   }
   int getX() const { return x; }
   int getY() const { return y; }
};
 
// To compare two points
class myComparator
{
public:
    int operator() (const Point& p1, const Point& p2)
    {
        return p1.getX() > p2.getX();
    }
};

int main() {
priority_queue<Point,vector<Point>,myComparator> pq;
pq.push(Point(2,3));
pq.push(Point(3,4));
return 0;
}

If I want to create a min-heap based on smaller value of x in every Point object. Why is it p1.getX() > p2.getX() and not p1.getX() < p2.getX() since I think p1 is the parent and p2 is the child and then parent should be less than child in min-heap. Please clear my confusion.

Upvotes: 1

Views: 1293

Answers (1)

Simon Kraemer
Simon Kraemer

Reputation: 5680

See std::priority_queue:

template<
   class T,
   class Container = std::vector<T>,
   class Compare = std::less<typename Container::value_type>
class priority_queue;

...

A priority queue is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.

A user-provided Compare can be supplied to change the ordering, e.g. using std::greater would cause the smallest element to appear as the top().

By default std::priority_queue uses the std::less comparator to sort the priority queue in a way that elements with higher values are prioritized.

If you want smaller values to be handled first, you need to inverse that function by providing a comparator that return a lower rank the higher the value is.

Upvotes: 3

Related Questions