C++ 中的堆和优先队列

在本文中，我们将介绍 C++ 中的堆和优先队列。堆是一种数据结构，可以高效地处理动态的优先级数据。而优先队列则是基于堆实现的一种抽象数据类型，能够以任意顺序插入元素，并按照一定的优先级顺序取出元素。

阅读更多：C++ 教程

堆的概念和特点

堆是一棵被完全填满的二叉树，且满足堆特性：对于每个节点，父节点的优先级要比子节点高。在 C++ 中，堆可以通过使用 std::priority_queue 来实现。std::priority_queue 是一个模板类，可以用于存储各种类型的元素，并按照它们的优先级自动排序。

下面是一个简单的例子，展示了如何使用 std::priority_queue 来创建堆以及添加和获取元素：

#include <iostream>
#include <queue>

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

    heap.push(5);
    heap.push(9);
    heap.push(3);
    heap.push(12);

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

    return 0;
}

上述代码创建了一个存储整数类型的堆，并依次插入了四个元素。然后，通过循环获取堆顶的元素并将其弹出，直到堆为空。输出结果为：“12 9 5 3”。

堆的应用场景

堆广泛应用于处理优先级队列、定时器、调度程序以及图算法等。在优先级队列中，堆可以高效地添加和删除元素，并且保证了每次取出的元素为最高优先级的元素。这使得堆成为处理大量数据中的高优先级任务的理想数据结构。

下面是一个实际的应用场景，展示了如何使用堆来解决问题：

假设有一个商城的订单系统，需要按照订单金额的大小来获取前 N 个订单。使用堆可以高效地实现该需求，以下是一段示例代码：

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

struct Order {
    int id;
    double amount;

    bool operator<(const Order& other) const {
        return amount < other.amount;
    }
};

int main() {
    std::vector<Order> orders = {
        {1, 100.0},
        {2, 50.0},
        {3, 75.0},
        {4, 200.0},
        {5, 150.0}
    };

    std::priority_queue<Order, std::vector<Order>> heap;

    for (const auto& order : orders) {
        heap.push(order);

        if (heap.size() > 3) {
            heap.pop();
        }
    }

    std::cout << "Top 3 orders:" << std::endl;

    while (!heap.empty()) {
        std::cout << "Order ID: " << heap.top().id << ", Amount: " << heap.top().amount << std::endl;
        heap.pop();
    }

    return 0;
}

上述代码通过定义一个自定义的 Order 结构体，并重载了 < 运算符来确定订单的优先级。然后，将订单依次插入堆中，同时保持堆的大小为 3，以满足需求。最后，输出堆中的前 3 个订单。

优先队列的特点和操作

优先队列是一个能够在任意位置插入元素，并以一定优先级删除元素的队列。它是由堆来实现的，因此其插入和删除的时间复杂度为 O(log N)。

常见的优先队列操作包括：
– push：将元素插入优先队列中；
– pop：删除优先队列中的前端元素；
– top：获取优先队列中的前端元素；
– empty：判断优先队列是否为空；
– size：获取优先队列中元素的个数。

下面是一个示例代码，展示了如何操作优先队列：

#include <iostream>
#include <queue>

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

    pq.push(5);
    pq.push(9);
    pq.push(3);

    std::cout << "Top element: " << pq.top() << std::endl; // 输出：9

    pq.pop();

    std::cout << "Top element after pop: " << pq.top() << std::endl; // 输出：5

    std::cout << "Is the priority queue empty? " << (pq.empty() ? "Yes" : "No") << std::endl; // 输出：No

    std::cout << "Size of the priority queue: " << pq.size() << std::endl; // 输出：2

    return 0;
}

上述代码通过 std::priority_queue 创建了一个优先队列，然后依次插入了三个元素。接下来，获取了队列的前端元素并输出，之后进行了一次删除操作，并再次获取前端元素并输出。最后，判断了优先队列是否为空，并获取了队列中元素的个数。

总结

本文介绍了 C++ 中的堆和优先队列。堆是一种能够高效处理动态优先级数据的数据结构，而优先队列则是基于堆实现的一种抽象数据类型。堆广泛应用于处理优先级队列、定时器、调度程序以及图算法等场景。优先队列具有 push、pop、top、empty 和 size 等常见操作，能够高效地插入和删除元素，并按照一定的优先级获取元素。通过深入了解和应用堆和优先队列，我们可以提高 C++ 程序的性能和效率。