优先队列 (Priority Queue)

优先队列 (Priority Queue) 简介

优先队列 (Priority Queue) 是一种特殊的队列，在优先队列中，元素被赋予优先级。当需要从队列中取出元素时，优先级最高的元素会最先被取出。这与普通的先进先出 (FIFO) 队列不同，在普通队列中，元素被取出的顺序与它们进入队列的顺序相同。优先队列中的元素出队顺序是由它们的优先级决定的，而不是它们在队列中的位置。

优先队列是如何实现的：

优先队列有多种实现方式，其中一些常见的包括：

• 链表 (Linked Lists)：可以使用排序的或未排序的链表来实现优先队列。
  • 在未排序的链表中，插入新元素很快 (O(1))，但查找最高优先级的元素需要遍历整个列表 (O(n))。
  • 在排序的链表中，查找最高优先级的元素很快 (O(1)，通常在链表头部)，但插入新元素需要找到正确的位置并插入，这可能需要 O(n) 的时间。
• 堆 (Heaps)：堆是实现优先队列的一种非常高效的方式。堆通常是一种完全二叉树，并满足堆属性：
  • 最小堆 (Min-Heap)：每个节点的值都小于或等于其子节点的值，因此根节点是最小值。
  • 最大堆 (Max-Heap)：每个节点的值都大于或等于其子节点的值，因此根节点是最大值。 使用堆实现的优先队列通常提供以下操作：
  • 插入 (Enqueue)：将新元素添加到堆的末尾，然后通过**“上浮” (heapify up)** 操作来恢复堆属性。
  • 删除最高优先级元素 (Dequeue)：移除根节点（最高优先级元素），然后将堆的最后一个元素移动到根节点，并通过**“下沉” (heapify down)** 操作来恢复堆属性。 使用堆实现优先队列，插入和删除操作的时间复杂度通常为 O(log n)，其中 n 是优先队列中元素的数量。
• 标准模板库 (STL) 中的 priority_queue：在 C++ 的 STL 中，priority_queue 默认情况下是使用 vector 作为底层容器，并使用 最大堆 (max-heap) 来实现的。用户也可以选择使用 deque 作为底层容器。在插入元素时，priority_queue 会使用一个比较函数 (comparator) 来维护队列中元素的优先级顺序，默认是使用 < 运算符，使得值最大的元素具有最高的优先级。用户也可以通过提供自定义的比较函数（例如 greater<T> 来实现最小堆）来改变优先级规则。

简单介绍：

优先队列在许多场景中都非常有用，例如：

• 任务调度：根据任务的优先级来决定先执行哪个任务。
• 事件驱动模拟：按照事件发生的优先级（通常是时间）来处理事件。
• 图算法：例如 Dijkstra 算法和 Prim 算法在实现中会用到优先队列来高效地选择下一个要处理的节点或边。

总而言之，优先队列是一种根据元素的优先级来管理元素的队列，通常使用堆数据结构来实现，以保证高效的插入和删除最高优先级元素的操作。

成员函数

demo程序

#include <iostream>
#include <queue>
#include <vector>
#include <functional> // greater<>

using namespace std;

int main() {
    // 创建一个存储整数的优先队列 (默认是最大堆)
    priority_queue<int> maxHeap;

    // 插入元素
    maxHeap.push(3);
    maxHeap.push(1);
    maxHeap.push(4);
    maxHeap.push(1);
    maxHeap.push(5);
    maxHeap.push(9);
    maxHeap.push(2);

    cout << "最大堆中的元素 (优先级降序):" << endl;
    while (!maxHeap.empty()) {
        cout << maxHeap.top() << " ";
        maxHeap.pop();
    }
    cout << endl << endl;

    // 使用 vector 初始化优先队列 (默认是最大堆)
    vector<int> nums1 = {5, 1, 8, 2, 9};
    priority_queue<int> maxHeap2(nums1.begin(), nums1.end());

    cout << "使用 vector 初始化的最大堆中的元素 (优先级降序):" << endl;
    while (!maxHeap2.empty()) {
        cout << maxHeap2.top() << " ";
        maxHeap2.pop();
    }
    cout << endl << endl;

    // 创建一个存储整数的最小堆 (使用 greater<int>)
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // 插入元素
    minHeap.push(3);
    minHeap.push(1);
    minHeap.push(4);
    minHeap.push(1);
    minHeap.push(5);
    minHeap.push(9);
    minHeap.push(2);

    cout << "最小堆中的元素 (优先级升序):" << endl;
    while (!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }
    cout << endl << endl;

    // 使用数组初始化最小堆
    int arr[] = {7, 2, 6, 3, 4};
    priority_queue<int, vector<int>, greater<int>> minHeap2(arr, arr + sizeof(arr) / sizeof(arr));

    cout << "使用数组初始化的最小堆中的元素 (优先级升序):" << endl;
    while (!minHeap2.empty()) {
        cout << minHeap2.top() << " ";
        minHeap2.pop();
    }
    cout << endl;

    return 0;
}

程序说明:

• 程序首先包含了必要的头文件 <iostream>, <queue>, <vector>, 和 <functional>.
• maxHeap 是一个默认构造的 priority_queue<int>，它是一个最大堆，因此优先级最高的（值最大的）元素会最先被 top() 返回和 pop() 移除.
• 程序演示了如何使用 push() 插入元素，top() 查看最高优先级元素，以及 pop() 移除最高优先级元素.
• maxHeap2 展示了如何使用一个 vector 的迭代器范围来初始化一个优先队列.
• minHeap 是一个最小堆，通过在模板参数中指定 greater<int> 作为比较函数对象来实现。这意味着优先级最高的是值最小的元素.
• 程序同样演示了 minHeap 的 push(), top(), 和 pop() 操作。
• minHeap2 展示了如何使用一个 C 风格的数组来初始化一个最小堆.

这个程序展示了 priority_queue 的基本用法，包括创建不同类型的优先队列（最大堆和最小堆），插入、访问和移除元素，以及如何使用已有的数据结构进行初始化.