C++ priority_queue用法优先队列自定义排序-C++-PHP中文网

priority_queue默认为最大堆，通过自定义比较器可实现最小堆或复杂排序逻辑，如用std::greater或自定义functor、lambda按特定规则排序。

c++ priority_queue用法优先队列自定义排序

priority_queue

登录后复制

在C++里默认是个最大堆，也就是说，它总是把最大的元素放在最前面，你一取就能拿到。但很多时候，我们需要的不是最大的，而是最小的，或者说，我们对“大小”的定义跟它默认的不一样。这时候，我们就需要给它一个“指南针”，告诉它怎么判断谁的优先级更高，这个指南针就是自定义排序。本质上，就是通过提供一个特定的比较器（comparator），来改变它内部堆的组织方式，让它按我们的规矩来排队。

解决方案

priority_queue

登录后复制

是一个容器适配器，它基于底层容器（默认是

std::vector

登录后复制

）和比较器（默认是

std::less<T>

登录后复制

）来构建。要自定义排序，关键就在于修改它的第三个模板参数——

Compare

登录后复制

。

实现最小堆（Min-Heap） 这是最常见的自定义需求。

priority_queue

登录后复制

默认用

std::less<T>

登录后复制

来比较，这意味着如果

a < b

登录后复制

，那么

登录后复制

的优先级就比

登录后复制

低，

登录后复制

会被放在更前面（形成最大堆）。如果想实现最小堆，我们希望

a > b

登录后复制

时，

登录后复制

的优先级比

登录后复制

低，这样小的元素才能浮到顶部。所以，我们用

std::greater<T>

登录后复制

作为比较器。

#include <iostream>
#include <queue>
#include <vector>
#include <functional> // For std::greater

void minHeapExample() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
    min_pq.push(3);
    min_pq.push(1);
    min_pq.push(4);
    min_pq.push(1);
    min_pq.push(5);

    std::cout << "Min-Heap elements (smallest first): ";
    while (!min_pq.empty()) {
        std::cout << min_pq.top() << " ";
        min_pq.pop();
    }
    std::cout << std::endl; // Output: 1 1 3 4 5
}

登录后复制

为自定义类型实现排序 当你的队列里放的是自定义的结构体或类对象时，比如一个

Point

登录后复制

，你想根据它的某个成员变量（比如

登录后复制

坐标）来决定优先级，这就需要更灵活的自定义比较器了。你可以使用：

自定义结构体/类作为比较器（Functor） 定义一个结构体，重载

operator()

登录后复制

，让它接收两个你的对象，并返回一个

bool

登录后复制

值，表示第一个对象是否“小于”第二个对象（即优先级是否更低）。记住，

priority_queue

登录后复制

会根据这个“小于”来构建一个最大堆。如果你想让

登录后复制

值小的优先级高（即最小堆），那么你的

operator()

登录后复制

应该返回

a.x > b.x

登录后复制

。

#include <iostream>
#include <queue>
#include <vector>

struct MyPoint {
    int x;
    int y;

    // 构造函数
    MyPoint(int x_val, int y_val) : x(x_val), y(y_val) {}

    // 用于打印
    void print() const {
        std::cout << "(" << x << "," << y << ")";
    }
};

// 自定义比较器：根据x值，x值越大优先级越高（最大堆）
struct CompareMyPointMaxX {
    bool operator()(const MyPoint& a, const MyPoint& b) const {
        return a.x < b.x; // 如果a的x小于b的x，则a的优先级更低，b会排在前面
    }
};

// 自定义比较器：根据x值，x值越小优先级越高（最小堆）
struct CompareMyPointMinX {
    bool operator()(const MyPoint& a, const MyPoint& b) const {
        return a.x > b.x; // 如果a的x大于b的x，则a的优先级更低，b会排在前面
    }
};

void customObjectExample() {
    std::priority_queue<MyPoint, std::vector<MyPoint>, CompareMyPointMaxX> pq_maxX;
    pq_maxX.push(MyPoint(10, 20));
    pq_maxX.push(MyPoint(5, 30));
    pq_maxX.push(MyPoint(15, 10));

    std::cout << "Custom Max-Heap by X: ";
    while (!pq_maxX.empty()) {
        pq_maxX.top().print();
        std::cout << " ";
        pq_maxX.pop();
    }
    std::cout << std::endl; // Output: (15,10) (10,20) (5,30)

    std::priority_queue<MyPoint, std::vector<MyPoint>, CompareMyPointMinX> pq_minX;
    pq_minX.push(MyPoint(10, 20));
    pq_minX.push(MyPoint(5, 30));
    pq_minX.push(MyPoint(15, 10));

    std::cout << "Custom Min-Heap by X: ";
    while (!pq_minX.empty()) {
        pq_minX.top().print();
        std::cout << " ";
        pq_minX.pop();
    }
    std::cout << std::endl; // Output: (5,30) (10,20) (15,10)
}

登录后复制

使用Lambda表达式（C++11及更高版本） 这是现代C++中非常简洁和灵活的方式。你可以在

priority_queue

登录后复制

的构造函数中直接传入一个lambda表达式。需要注意的是，因为lambda表达式本身是一个匿名类型，你不能直接把它作为模板参数。你需要先定义一个

auto

登录后复制

变量来捕获这个lambda，或者使用

decltype

登录后复制

。更常见且推荐的做法是，直接在构造时提供lambda，让编译器推导。

#include <iostream>
#include <queue>
#include <vector>
#include <functional> // For std::function (optional, but good for understanding)

struct Task {
    int id;
    int priority; // 优先级值，越小表示优先级越高

    Task(int i, int p) : id(i), priority(p) {}

    void print() const {
        std::cout << "[ID:" << id << ",P:" << priority << "]";
    }
};

void lambdaCustomSortExample() {
    // Lambda作为比较器：根据Task的priority值，值越小优先级越高（最小堆）
    // 注意：priority_queue默认是最大堆行为，所以如果希望priority值小的排在前面，
    // 那么lambda应该返回 'a.priority > b.priority'，表示a的优先级更低
    auto cmp = [](const Task& a, const Task& b) {
        return a.priority > b.priority; // 如果a的优先级值比b大，则a的优先级更低
    };

    // 声明priority_queue时，需要将lambda的类型作为模板参数
    // 通常做法是定义一个局部变量来捕获lambda，然后用decltype获取其类型
    std::priority_queue<Task, std::vector<Task>, decltype(cmp)> task_pq(cmp);

    task_pq.push(Task(101, 5)); // 低优先级
    task_pq.push(Task(102, 1)); // 高优先级
    task_pq.push(Task(103, 3)); // 中优先级

    std::cout << "Tasks by priority (smallest priority value first): ";
    while (!task_pq.empty()) {
        task_pq.top().print();
        std::cout << " ";
        task_pq.pop();
    }
    std::cout << std::endl; // Output: [ID:102,P:1] [ID:103,P:3] [ID:101,P:5]
}

登录后复制

在实际项目中，我个人更倾向于使用lambda，因为它写起来快，而且如果比较逻辑只用一次，代码也更集中。但如果比较逻辑复杂或者需要在多个地方复用，一个独立的functor类会是更好的选择，因为它有名字，可读性更强。

为什么需要自定义排序？默认行为不够用吗？

这个问题问得好，直击核心。默认的

priority_queue

登录后复制

是最大堆，它能很好地解决“总是想拿到当前最大值”的问题。比如，你有一堆任务，每个任务有个“重要性”评分，你总是想优先处理最重要的。这种场景，默认行为完全够用。

立即学习“C++免费学习笔记（深入）”；

但现实世界可没那么简单，优先级这东西，定义起来千变万化。

想想看，如果你在实现一个最短路径算法，比如Dijkstra，你需要一个优先队列来存储待处理的节点，并且每次都取出“距离源点最近”的那个节点。这里的“最近”显然是“最小”的概念，而默认的最大堆就帮不上忙了。你需要一个最小堆。

再比如，你可能在处理一个复杂的排班系统，员工有多个属性：工龄、绩效、加班意愿等等。你可能需要根据这些属性的组合来决定谁的优先级更高。比如，工龄越长优先级越高，如果工龄相同，再看绩效，绩效越高优先级越高。这种多条件、自定义逻辑的排序，默认的

int

登录后复制

或

double

登录后复制

比较根本无法满足，你必须自己写规则。

所以，默认行为不是不够用，而是它只覆盖了最基础、最普遍的需求。一旦你的“优先级”定义超出了简单的数值大小，或者你需要的是“最小”而不是“最大”时，自定义排序就成了你的救星。它赋予了你对数据“排序逻辑”的完全控制权，这在解决复杂算法问题和业务逻辑时，简直是不可或缺的能力。

如何为复杂数据结构实现自定义排序？

为复杂数据结构实现自定义排序，通常意味着你需要根据对象的多个成员变量，或者一些计算出来的属性来决定它们的相对顺序。这比简单的数值比较要精妙得多。

我一般会这么做：

序列猴子开放平台

具有长序列、多模态、单模型、大数据等特点的超大规模语言模型

查看详情

明确排序规则： 这是第一步，也是最关键的一步。你需要清晰地定义“A比B优先级高”到底意味着什么。例如，对于一个
```
Player
```
登录后复制
对象，你可能想先按等级（高等级优先），等级相同再按经验值（高经验值优先），经验值再相同就按ID（小ID优先）。

选择比较器实现方式：

Functor（函数对象）： 定义一个独立的结构体，重载
```
operator()
```
登录后复制
。这种方式的好处是，比较逻辑被封装在一个有名字的类型里，可读性强，方便复用。如果你的比较器需要保存一些状态（比如一个阈值），functor也能轻松实现。
Lambda表达式： 如果比较逻辑比较简单，或者只在特定地方使用一次，lambda表达式是绝佳的选择。它简洁、直接，代码内联，避免了额外定义一个类的开销。

我们来用一个更复杂的例子：

Student

登录后复制

，有

score

登录后复制

和

id

登录后复制

。我们希望

score

登录后复制

高的优先级高，如果

score

登录后复制

相同，

id

登录后复制

小的优先级高。

#include <iostream>
#include <queue>
#include <vector>

struct Student {
    int id;
    int score;

    Student(int i, int s) : id(i), score(s) {}

    void print() const {
        std::cout << "[ID:" << id << ",Score:" << score << "]";
    }
};

// 方法一：使用Functor
struct CompareStudent {
    bool operator()(const Student& a, const Student& b) const {
        // 优先比较分数：分数高的优先级高 (最大堆)
        if (a.score != b.score) {
            return a.score < b.score; // 如果a的分数比b低，则a的优先级更低
        }
        // 分数相同，比较ID：ID小的优先级高 (最小堆)
        return a.id > b.id; // 如果a的ID比b大，则a的优先级更低
    }
};

void complexObjectFunctorExample() {
    std::priority_queue<Student, std::vector<Student>, CompareStudent> student_pq;
    student_pq.push(Student(101, 90));
    student_pq.push(Student(102, 95));
    student_pq.push(Student(103, 90)); // 分数相同，ID不同
    student_pq.push(Student(104, 85));

    std::cout << "Students by Score (desc), then ID (asc): ";
    while (!student_pq.empty()) {
        student_pq.top().print();
        std::cout << " ";
        student_pq.pop();
    }
    std::cout << std::endl; // Output: [ID:102,Score:95] [ID:101,Score:90] [ID:103,Score:90] [ID:104,Score:85] (这里ID101在103前面，因为101的ID更小，在分数相同的情况下优先级更高)
}

// 方法二：使用Lambda表达式
void complexObjectLambdaExample() {
    auto cmp_lambda = [](const Student& a, const Student& b) {
        if (a.score != b.score) {
            return a.score < b.score; // 分数高的优先级高
        }
        return a.id > b.id; // ID小的优先级高
    };

    std::priority_queue<Student, std::vector<Student>, decltype(cmp_lambda)> student_pq_lambda(cmp_lambda);
    student_pq_lambda.push(Student(201, 88));
    student_pq_lambda.push(Student(202, 92));
    student_pq_lambda.push(Student(203, 88));
    student_pq_lambda.push(Student(204, 92)); // 分数相同，ID不同

    std::cout << "Students by Score (desc), then ID (asc) (Lambda): ";
    while (!student_pq_lambda.empty()) {
        student_pq_lambda.top().print();
        std::cout << " ";
        student_pq_lambda.pop();
    }
    std::cout << std::endl; // Output: [ID:202,Score:92] [ID:204,Score:92] [ID:201,Score:88] [ID:203,Score:88]
}

登录后复制

无论是Functor还是Lambda，核心都是实现一个二元谓词（binary predicate），它接收两个对象，并返回

true

登录后复制

如果第一个对象应该被认为“小于”第二个对象（即优先级更低）。这个“小于”的定义完全由你掌控。

自定义排序时常见的误区与性能考量

在自定义

priority_queue

登录后复制

的排序逻辑时，我见过不少人，包括我自己，会踩一些坑。同时，性能也是一个需要注意的点。

常见误区：

最大堆与最小堆的逻辑混淆： 这是最普遍的。
```
priority_queue
```
登录后复制
默认行为是最大堆，意味着
```
top()
```
登录后复制
总是最大的。你的比较器
```
Compare
```
登录后复制
，如果
```
cmp(a, b)
```
登录后复制
返回
```
true
```
登录后复制
，则表示
```
a
```
登录后复制
的优先级比
```
b
```
登录后复制
低，
```
b
```
登录后复制
会排在
```
a
```
登录后复制
前面。
- 如果你想让“值越小优先级越高”（最小堆），那么当
```
a > b
```
  登录后复制
  时，
```
a
```
  登录后复制
  的优先级应该更低，所以
```
cmp(a, b)
```
  登录后复制
  应该返回
```
true
```
  登录后复制
  。例如，
```
return a.value > b.value;
```
  登录后复制
  。
- 如果你想让“值越大优先级越高”（最大堆），那么当
```
a < b
```
  登录后复制
  时，
```
a
```
  登录后复制
  的优先级应该更低，所以
```
cmp(a, b)
```
  登录后复制
  应该返回
```
true
```
  登录后复制
  。例如，
```
return a.value < b.value;
```
  登录后复制
  。初学者经常会搞反，导致结果和预期相反。我通常会拿
```
std::less<int>
```
  登录后复制
  和
```
std::greater<int>
```
  登录后复制
  来做个实验，看它们各自对应最大堆还是最小堆，然后根据这个理解去推导自定义逻辑。
比较器不满足严格弱序（Strict Weak Ordering）： 这是算法正确性的基石。一个有效的比较器必须满足：
- 非自反性：
```
cmp(x, x)
```
  登录后复制
  必须为
```
false
```
  登录后复制
  。
- 反对称性： 如果
```
cmp(x, y)
```
  登录后复制
  为
```
true
```
  登录后复制
  ，则
```
cmp(y, x)
```
  登录后复制
  必须为
```
false
```
  登录后复制
  。
- 传递性： 如果
```
cmp(x, y)
```
  登录后复制
  为
```
true
```
  登录后复制
  且
```
cmp(y, z)
```
  登录后复制
  为
```
true
```
  登录后复制
  ，则
```
cmp(x, z)
```
  登录后复制
  必须为
```
true
```
  登录后复制
  。
- 等价性传递： 如果
```
x
```
  登录后复制
  和
```
y
```
  登录后复制
  等价（即
```
!cmp(x, y) && !cmp(y, x)
```
  登录后复制
  ），且
```
y
```
  登录后复制
  和
```
z
```
  登录后复制
  等价，则
```
x
```
  登录后复制
  和
```
z
```
  登录后复制
  也必须等价。违反这些规则会导致
```
priority_queue
```
  登录后复制
  内部的堆结构被破坏，从而产生不可预测的错误，调试起来会非常痛苦。

参数传递效率问题： 在比较器中，如果你的自定义对象比较大，确保参数是以

const T&

登录后复制

的形式传递，而不是

登录后复制

（按值传递）。按值传递会产生不必要的对象拷贝，这在频繁的比较操作中会显著降低性能。

// 错误示例：按值传递，可能导致性能问题
struct BadCompare {
    bool operator()(MyBigObject a, MyBigObject b) const { // 注意这里没有const &
        // ...
        return a.value < b.value;
    }
};

// 正确示例：按const引用传递
struct GoodCompare {
    bool operator()(const MyBigObject& a, const MyBigObject& b) const {
        // ...
        return a.value < b.value;
    }
};

登录后复制

性能考量：

比较器复杂度：
```
priority_queue
```
登录后复制
的
```
push
```
登录后复制
和
```
pop
```
登录后复制
操作的时间复杂度是
```
O(log N)
```
登录后复制
，其中
```
N
```
登录后复制
是队列中的元素数量。这个
```
log N
```
登录后复制
是基于比较操作的次数。如果你的自定义比较器内部执行了非常复杂的计算（比如遍历一个列表，或者进行网络请求——当然，你不会这么做，但理论上），那么每次比较的常数时间就会变大，从而拉长整体操作时间。所以，设计比较器时，尽量保持其内部逻辑简洁高效。避免在比较器中