Custom Compare Function for Priority Queue

Question

I was implementing a custom compare function for priority queue and saw a difference between the compare function of sort and priority queue STL.

Suppose, we have couple of points(x, y) and for those points we have a user defined class.

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

And the custom compare function:

class myComparator
{
public:
    int operator() (const Point& p1, const Point& p2)
    {
        return p1.getX() > p2.getX();
    }
};

Now, if we pass the compare function to sort STL, then it will sort the points in descending order of x co-ordinate.

int main ()
{
    vector<Point>v;

    v.push_back(Point(10, 1));
    v.push_back(Point(1, 5));
    v.push_back(Point(2, 1));

    sort(v.begin(), v.end(), myComparator());

    for(auto p: v)
    {
        cout << "(" << p.getX() << ", " << p.getY() << ")"<<endl;
    }

    return 0;
}

Output:

(10, 1)
(2, 1)
(1, 5)

Now, if I apply the same compare function for priority queue, it will have the points in descending order. Basically, it is working as min heap.

int main ()
{
    priority_queue <Point, vector<Point>, myComparator > pq;

    pq.push(Point(10, 2));
    pq.push(Point(2, 1));
    pq.push(Point(1, 5));

    while (pq.empty() == false)
    {
        Point p = pq.top();
        cout << "(" << p.getX() << ", " << p.getY() << ")";
        cout << endl;
        pq.pop();
    }

    return 0;
}

Output:

(1, 5)
(2, 1)
(10, 2)

I was expecting that the points will be ordered like the sort function as in the custom compare function I have written like below:

p1.getX() > p2.getX()

Why the compare function works differently in priority queue?

Answer 1

std::priority_queue

Note that the Compare parameter is defined such that it returns true if its first argument comes before its second argument in a weak ordering. But because the priority queue outputs largest elements first, the elements that "come before" are actually output last. That is, the front of the queue contains the "last" element according to the weak ordering imposed by Compare.