C++ priority_queue用法优先队列自定义排序（自定义.队列.用法.排序.优先...）

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

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

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

想想看，如果你在实现一个最短路径算法，比如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
```
是基于比较操作的次数。如果你的自定义比较器内部执行了非常复杂的计算（比如遍历一个列表，或者进行网络请求——当然，你不会这么做，但理论上），那么每次比较的常数时间就会变大，从而拉长整体操作时间。所以，设计比较器时，尽量保持其内部逻辑简洁高效。避免在比较器中

以上就是C++ priority_queue用法优先队列自定义排序的详细内容，更多请关注知识资源分享宝库其它相关文章！

C++ priority_queue用法优先队列自定义排序（自定义.队列.用法.排序.优先...）

最近发表

标签列表

C++ priority_queue用法 优先队列自定义排序（自定义.队列.用法.排序.优先...）

相关阅读

C++机器人开发 ROS框架环境配置（机器人.框架.配置.环境.开发...）

在Visual Studio中如何调试C++内存错误（调试.内存.错误.Visual.Studio...）

C++函数返回指针 局部变量地址问题（指针.变量.局部.函数.返回...）

C++游戏引擎开发 简单渲染循环实现（渲染.循环.简单.引擎.开发...）

C++金融回测环境 历史数据高速读取优化（历史数据.读取.优化.环境.金融...）

C++异常资源清理 局部对象析构保证（局部.清理.异常.对象.保证...）

最近发表

标签列表

C++ priority_queue用法优先队列自定义排序（自定义.队列.用法.排序.优先...）

C++函数返回指针局部变量地址问题（指针.变量.局部.函数.返回...）

C++游戏引擎开发简单渲染循环实现（渲染.循环.简单.引擎.开发...）

C++金融回测环境历史数据高速读取优化（历史数据.读取.优化.环境.金融...）

C++异常资源清理局部对象析构保证（局部.清理.异常.对象.保证...）