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

Question

我有一个点 Class 并且正在创建一个 min-heap 点 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;
}

如果我想根据每个点 object 中较小的 x 值创建一个 min-heap。为什么是 p1.getX() > p2.getX() 而不是 p1.getX() < p2.getX() 因为我认为 p1 是 parent 而 p2 是child 然后 parent 应该小于 min-heap 中的 child。请解开我的疑惑。

Answer 1

参见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().

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

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

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

Min Heap Custom Comparator in C++

c++

heap

stl