c++中的最小堆自定义比较器

Question

我有一个点类，我正在创建一个最小堆的点对象。

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

如果我想在每个Point对象中创建一个基于较小x值的最小堆。为什么是p1.getX()>p2.getX()而不是p1.getX() <p2。getx()因为我认为p1是父结点p2是子结点那么父结点在最小堆中应该小于子结点。请为我解惑。>

Answer 1

参见std::priority_queue:

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

…

优先级队列是一个容器适配器，它提供对最大的常量时间查找。(默认情况下)元素，以对数插入和提取为代价。

可以使用用户提供的Compare来改变顺序，例如，使用std::greater会导致最小的元素出现在top()中。

默认情况下，std::priority_queue使用std::less比较器对优先级队列进行排序，使具有较高值的元素优先级.

如果您希望先处理较小的值，则需要通过提供一个比较器来反转该函数，该比较器返回值越高的较低的秩。