正确使用Cpriority_queue比较器

Question

这个问题最近在一次采访中被问到。

public interface PointsOnAPlane {

/**
 * Stores a given point in an internal data structure
 */
void addPoint(Point point);

/**
 * For given 'center' point returns a subset of 'm' stored points that are
 * closer to the center than others.
 *
 * E.g. Stored: (0, 1) (0, 2) (0, 3) (0, 4) (0, 5)
 *
 * findNearest(new Point(0, 0), 3) -> (0, 1), (0, 2), (0, 3)
 */
vector<Point> findNearest(vector<Point> points, Point center, int m);

}

这是我使用的以下方法

1）创建一个最大堆priority_queue来存储最近的点priority_queue

2)迭代点向量，如果优先级队列大小，则推送一个点

3)如果size == m，则将队列顶部与当前点进行比较，并在必要时弹出

for(int i=0;i<points.size();i++)
{
    if(pq.size() < m)
    {
       pq.push(points[i]);
    } 
    else
    {
       if(compareDistance(points[i],pq.top(),center))
       {
         pq.pop();
         pq.push(points[i]);
       }
    }
}

4） 最后，将优先级队列的内容放入向量并返回。

我应该如何编写comp和compareDistance比较器，以允许我最初存储m个点，然后将当前点与顶部的点进行比较？




Answer 1

我认为您的方法可以改变，以便以不同的方式使用priority_queue。代码变得有点复杂，因为for循环中有一个if语句，并且这个if语句控制何时添加到priority_queue。为什么不先将所有点添加到priority_queue，然后弹出m点？让priority_queue完成所有工作。

使用＜code＞priority_queue＜/code＞实现＜code＞findNearest＜/code＞功能的关键在于实现比较器可以是捕获中心参数的lambda。所以你可以这样做：

#include <queue>
#include <vector>
using namespace std;

struct Point { int x, y; };

constexpr int distance(const Point& l, const Point& r)
{
    return (l.x - r.x)*(l.x - r.x) + (l.y - r.y)*(l.y - r.y);
}

vector<Point> findNearest(const vector<Point>& points, Point center, int m)
{
    auto comparator = [center](const Point& l, const Point& r) {
        return distance(l, center) > distance(r, center);
    };

    priority_queue<Point, vector<Point>, decltype(comparator)> pq(comparator);

    for (auto&& p : points) {
        pq.emplace(p);
    }

    vector<Point> result;
    for (int i = 0; i < m; ++i) {
        result.push_back(pq.top());
        pq.pop();
    }

    return result;
}

在面试环境中，谈论算法中的缺陷也很好。

• 这个实现在O（nlogng）中运行。将会有一个聪明的算法来击败这个运行时间，特别是因为您只需要最近的m点。
• 由于队列的原因，它使用了O（n）更多的空间，我们应该能够做得更好。这个函数中真正发生的是一个排序，排序可以就地实现。
• 容易发生整数溢出。一个好主意是在Point结构上使用模板。您还可以使用模板使point容器在findNeest函数中通用。容器只需要支持迭代。