基于KD树实现K近邻搜索：优先队列自定义比较器实现问询

刚好我之前在做KD树的K近邻搜索时也遇到过这个问题，咱们一步步来解决：

首先你得先纠正两个关键错误，再实现正确的比较逻辑：

1. 优先队列的声明方式错了 #

priority_queue的第三个模板参数是比较器的类型，不是实例！你原来写的comparator(query,d)是创建了一个对象，这不符合模板参数的要求。正确的做法是把comparator作为类型传入，然后在构造优先队列的时候，把带有query和d的比较器实例传进去。

2. 比较器的operator()返回值必须是bool #

C++标准库的优先队列要求比较器的operator()返回bool类型，用来定义严格弱序关系：返回true意味着第一个参数应该被放在第二个参数的后面（即优先级更低）。

完整的实现代码示例 #

#include <queue>
#include <vector>
#include <cmath>

// 自定义比较器类：用于比较两个点到查询点的距离平方
class DistanceComparator {
private:
    double* query_point; // 查询点
    int dim;             // 维度

public:
    // 构造函数：初始化查询点和维度
    DistanceComparator(double* q, int d) : query_point(q), dim(d) {}

    // 重载()运算符：实现比较逻辑
    // 注意：priority_queue默认是最大堆，所以我们让距离平方大的点优先级更高
    // 这样堆顶就是当前最远的点，超过K个时直接弹出堆顶即可
    bool operator()(double* point_a, double* point_b) const {
        // 计算点a到查询点的距离平方
        double dist_sq_a = 0.0;
        for (int i = 0; i < dim; ++i) {
            double diff = point_a[i] - query_point[i];
            dist_sq_a += diff * diff;
        }

        // 计算点b到查询点的距离平方
        double dist_sq_b = 0.0;
        for (int i = 0; i < dim; ++i) {
            double diff = point_b[i] - query_point[i];
            dist_sq_b += diff * diff;
        }

        // 返回true表示a的优先级低于b（即a应该排在b后面）
        // 这里我们要实现最大堆，所以距离平方大的点优先级更高
        return dist_sq_a < dist_sq_b;
    }
};

// 使用示例
int main() {
    int dim = 3; // 3维空间
    double query[] = {1.0, 2.0, 3.0}; // 查询点

    // 正确声明并构造优先队列：传入比较器实例
    std::priority_queue<double*, std::vector<double*>, DistanceComparator> 
        max_heap(DistanceComparator(query, dim));

    // 后续就可以往堆里添加点，维护K个最近邻了
    // ...
    return 0;
}

关键细节说明 #

• 为什么用距离平方？：计算平方根会带来额外的性能开销，而比较距离平方和比较实际距离的结果是完全一致的，所以在K近邻搜索中通常用距离平方来替代实际距离。
• 为什么用最大堆？：K近邻搜索需要维护最近的K个点，当堆的大小超过K时，我们直接弹出堆顶（当前最远的点），这样堆里始终保留的是最近的K个点，效率更高。如果你需要最小堆，只需要把operator()里的dist_sq_a < dist_sq_b改成dist_sq_a > dist_sq_b即可。
• 比较器必须是可拷贝构造的：标准库容器要求比较器满足可拷贝，这里我们的DistanceComparator成员是指针和int，默认拷贝构造函数就可以满足需求。

内容的提问来源于stack exchange，提问作者Newbie