C++之优先队列（priority_queue）

priority_queue 是 C++ 标准模板库（STL）中的一种容器适配器，它提供了一个基于优先级的队列。这意味着它存储的元素是按照一定的优先级进行排序的，每次访问队头元素都是当前队列中优先级最高的元素。

在 C++ 中，priority_queue 通常使用堆（heap）来实现，堆是一种特殊的二叉树结构，满足堆的性质。C++ 中的 priority_queue 默认使用大顶堆，也就是队头元素是最大的元素。你可以通过提供比较函数来使用小顶堆。

以下是一个简单的示例，演示了如何使用 priority_queue：

#include <iostream>
#include <queue>

int main() {
    // 创建一个大顶堆的 priority_queue
    std::priority_queue<int> maxHeap;

    // 插入元素
    maxHeap.push(10);
    maxHeap.push(30);
    maxHeap.push(20);

    // 访问队头元素
    std::cout << "Top element: " << maxHeap.top() << std::endl;

    // 弹出队头元素
    maxHeap.pop();

    // 访问新的队头元素
    std::cout << "Top element after pop: " << maxHeap.top() << std::endl;

    return 0;
}

在这个示例中，std::priority_queue 被创建为大顶堆，默认情况下，元素的比较使用 < 操作符。你可以通过提供自定义的比较函数来创建小顶堆。

例如，如果要创建一个小顶堆，可以这样做：

#include <iostream>
#include <queue>

// 自定义比较函数，使得小的元素优先级高
struct Compare {
    bool operator()(int a, int b) {
        return a > b;
    }
};

int main() {
    // 创建一个小顶堆的 priority_queue
    std::priority_queue<int, std::vector<int>, Compare> minHeap;

    // 插入元素
    minHeap.push(10);
    minHeap.push(30);
    minHeap.push(20);

    // 访问队头元素
    std::cout << "Top element: " << minHeap.top() << std::endl;

    // 弹出队头元素
    minHeap.pop();

    // 访问新的队头元素
    std::cout << "Top element after pop: " << minHeap.top() << std::endl;

    return 0;
}

这个例子中，Compare 结构体定义了自定义的比较函数，确保小的元素优先级更高。

组合实例：

#include <iostream>
#include <queue>

// 自定义比较函数，使得小的元素优先级高
struct Compare {
    bool operator()(int a, int b) {
        return a > b;
    }
};

int main() {
    // 创建一个大顶堆的 priority_queue
    std::priority_queue<int> maxHeap;

    // 插入元素
    maxHeap.push(10);
    maxHeap.push(30);
    maxHeap.push(20);

    // 访问队头元素
    std::cout << "Top Max element: " << maxHeap.top() << std::endl;

    // 弹出队头元素
    maxHeap.pop();

    // 访问新的队头元素
    std::cout << "Top Max element after pop: " << maxHeap.top() << std::endl;


    // 创建一个小顶堆的 priority_queue
    std::priority_queue<int, std::vector<int>, Compare> minHeap;

    // 插入元素
    minHeap.push(10);
    minHeap.push(30);
    minHeap.push(20);

    // 访问队头元素
    std::cout << "Top Min element: " << minHeap.top() << std::endl;

    // 弹出队头元素
    minHeap.pop();

    // 访问新的队头元素
    std::cout << "Top  Min element after pop: " << minHeap.top() << std::endl;

    return 0;
}