C++的优先队列priority_queue如何自定义排序

在C++中，std::priority_queue 是一个容器适配器，默认情况下它是一个最大堆，即队列顶部的元素是最大的，如果想自定义排序规则，可以通过提供一个自定义的比较函数或函数对象来实现

目录

仿函数

lambda表达式

 std::greater 或 std::less

仿函数

仿函数就是一个重载了括号运算符的结构体或者类

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

// 自定义比较函数
struct Compare {
    bool operator()(int a, int b) {
        return a > b; // 最小堆
    }
};

int main() {
    // 使用自定义比较函数声明优先队列
    std::priority_queue<int, std::vector<int>, Compare> minHeap;

    minHeap.push(3);

    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " ";
        minHeap.pop();
    }

    return 0;
}

lambda表达式

decltype(cmp) 用于获取 Lambda 表达式的类型

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

int main() {
    // 使用 Lambda 表达式作为比较函数
    auto cmp = [](int a, int b) { return a > b; };
    std::priority_queue<int, std::vector<int>, decltype(cmp)> minHeap(cmp);

    minHeap.push(4);

    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " ";
        minHeap.pop();
    }

    return 0;
}

还可以这样写，std::function 是一个通用的可调用类型包装器，可以封装任何类型的可调用对象（包括函数、Lambda、函数对象等）

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

using namespace std;

int main() {
    // 使用 Lambda 表达式作为比较器
    priority_queue<int, vector<int>, function<bool(int, int)>> pq(
        [](int a, int b) { return a > b; }  // 按升序排列（最小堆）
    );
    
    pq.push(5);
    
    // 输出队列中的元素
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    // 输出: 5 10 20 30  （按升序排列）
    
    return 0;
}

 std::greater 或 std::less

可以使用标准库中的比较函数对象，std::greater<int> 使得 priority_queue 成为一个最小堆，意思是元素越来越大

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

int main() {
    // 使用 std::greater 作为比较函数
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    minHeap.push(4);

    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " ";
        minHeap.pop();
    }

    return 0;
}