【C++】—— priority_queue与仿函数

在C++中，priority_queue（优先队列）是一个常用的容器适配器，用于存储一组元素并依据某种排序规则进行优先级的管理。与普通的队列不同，priority_queue会保证出队的元素是当前队列中优先级最高的元素。

在priority_queue的实现中，我们可以自定义排序规则，这就需要用到仿函数（Functor）。仿函数是一个重载了operator()的类实例，可以像普通函数那样被调用。

priority_queue的基本使用

首先，我们来看一下priority_queue的基本使用。默认情况下，priority_queue使用std::less作为排序准则，意味着它将元素以最大堆的形式存储：根节点是最大的元素。

以下是一个简单的示例：

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;

    pq.push(10);
    pq.push(20);
    pq.push(5);

    std::cout << "优先队列中的元素（顺序为高优先级到低优先级）: ";
    while (!pq.empty()) {
        std::cout << pq.top() << " "; // 打印优先队列的顶部元素
        pq.pop(); // 移除顶部元素
    }
    std::cout << std::endl;

    return 0;
}

在上述代码中，我们创建了一个优先队列pq，并逐个插入了元素。当我们从队列中取出元素时，输出的顺序是20 10 5，表明20是优先级最高的元素。

自定义排序规则

有时候我们可能需要根据不同的规则排序，比如求最小值而不是最大值。这时就需要自定义排序规则。我们可以通过创建一个仿函数来实现。以下是一个使用自定义仿函数的示例，它使得priority_queue按最小堆排序：

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

class Compare {
public:
    bool operator()(int a, int b) {
        return a > b; // 当a大于b时，返回true，表示a的优先级低于b
    }
};

int main() {
    std::priority_queue<int, std::vector<int>, Compare> minHeap;

    minHeap.push(10);
    minHeap.push(20);
    minHeap.push(5);

    std::cout << "最小优先队列中的元素（顺序为低优先级到高优先级）: ";
    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " "; // 打印优先队列的顶部元素
        minHeap.pop(); // 移除顶部元素
    }
    std::cout << std::endl;

    return 0;
}

在这个示例中，我们定义了一个Compare类，重载了operator()，使得优先队列遵循最小堆的规则。插入的元素10, 20, 5最终输出顺序为5 10 20，表明5是优先级最高的元素。

小结

通过以上示例，我们可以看到，priority_queue在处理需求时非常灵活，尤其是当我们需要根据特定规则进行排序时。通过仿函数，我们可以轻松地自定义元素的排序方式，使得priority_queue能根据我们的需求进行优先级管理。这种功能在很多算法和数据结构中都具有重要的应用，比如 Dijkstra 算法、A* 算法等。