深入了解 C++ 优先队列

2023-07-14
四川
本文字数：2006 字
阅读完需：约 7 分钟

简介：

在计算机科学中，优先队列是一种抽象数据类型，它与队列相似，但是每个元素都有一个相关的优先级。C++中的优先队列是一个容器适配器(container adapter)，它提供了一种在元素之间维护优先级的方法。

1、优先队列的基本概念

在计算机科学中，优先队列是一种抽象数据类型，它与队列相似，但是每个元素都有一个相关的优先级。在优先队列中，当我们执行插入操作时，我们将元素插入到队列中，并根据其优先级对其进行排序。在删除操作中，我们会删除优先级最高的元素，并把队列进行重新排序。优先队列通常使用堆来实现。

C++中的优先队列是一个容器适配器(container adapter)，它提供了一种在元素之间维护优先级的方法。使用 C++优先队列，你可以在队列头部添加新元素，并从队列头部移除元素。当添加元素时，它将根据元素的排序准则将其放置在适当的位置。

2、优先队列的使用方法

在 C++中，我们可以使用头文件"queue"中的 priority_queue 来创建一个优先队列。接下来是一个简单的代码示例，它说明了如何使用 priority_queue 创建一个整数类型的队列。

#include <iostream>#include <queue>
int main() {    std::priority_queue<int> pq;
    pq.push(1);    pq.push(2);    pq.push(3);        std::cout << "Queue Size : " << pq.size() << std::endl;    std::cout << "Top Element: " << pq.top() << std::endl;
    while(!pq.empty()) {        std::cout << pq.top() << std::endl;        pq.pop();    }    return 0;}

复制代码

在上面的代码中，我们首先包含头文件"queue"，并使用 std::priority_queue 来创建一个整数类型的优先队列。接下来，我们使用 push()方法向队列中添加元素。在添加元素后，我们可以使用 size()方法来检查队列的大小。我们还可以使用 top()方法获取队列的顶部元素。

在 while 循环中，我们使用 top()方法检查顶部元素，并使用 pop()方法从队列中删除它。

3、优先队列元素的排序规则

默认情况下，C++优先队列使用 std::less 来确定哪个元素具有更高的优先级。这意味着优先队列中的元素以升序排列。如果您想使用降序排列，您可以将 std::greater 用作参数。

接下来是一个降序排列的示例：

#include <iostream>#include <queue>
int main() {    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
    pq.push(3);    pq.push(2);    pq.push(1);        std::cout << "Queue Size : " << pq.size() << std::endl;    std::cout << "Top Element: " << pq.top() << std::endl;
    while(!pq.empty()) {        std::cout << pq.top() << std::endl;        pq.pop();    }    return 0;}

复制代码

在上述代码中，我们向 priority_queue 的构造函数中添加了第三个参数 std::greater。这表示我们正在使用降序排列。

4、元素的自定义排序

有时，您可能需要使用自定义排序规则将元素插入到 C++优先队列中。在这种情况下，您可以使用 lambda 表达式或者实现一个二元谓词(类似于比较函数)。

接下来是一个使用 lambda 表达式进行排序的示例：

#include <iostream>#include <queue>
struct custom_struct {    int priority;    std::string message;
    custom_struct(int priority_, std::string message_) : priority(priority_), message(message_) {}};
int main() {    auto comp = [](custom_struct a, custom_struct b) {return a.priority > b.priority;};    std::priority_queue<custom_struct, std::vector<custom_struct>, decltype(comp)> pq(comp);
    pq.push(custom_struct(1, "Hello"));    pq.push(custom_struct(2, "World"));    pq.push(custom_struct(3, "Priority"));        std::cout << "Queue Size : " << pq.size() << std::endl;    std::cout << "Top Element: " << pq.top().message << std::endl;
    while(!pq.empty()) {        std::cout << pq.top().message << std::endl;        pq.pop();    }    return 0;}

复制代码

在上述代码中，我们首先定义一个名为 custom_struct 的自定义结构体。接下来，我们使用 lambda 表达式定义了一个比较二元谓词。第三个参数是我们自定义的二元谓词。最后，我们创建了一个 custom_struct 类型的优先队列，并在其构造函数中使用 comp 参数，这将使用我们刚刚定义的比较谓词对元素进行排序。