C++中集合的优先队列及示例

在C++编程中，集合是一种常见的数据结构。而在集合的处理过程中，优先队列则是其中的一种经典应用。本文将介绍C++中集合的优先队列及示例。

什么是优先队列？

优先队列（Priority Queue）是一种特别的线性结构，它维护了一个元素集合，每个元素都有一个关键字。相对于普通的队列，优先队列中元素的插入和取出不仅考虑到时间的先后，还考虑到元素的关键字，优先队列可以保证最高优先级的元素先被取出。

在C++中，优先队列实现方式是通过堆（Heap）来实现，具体的实现方法在后续代码示例中会详细介绍。

C++中优先队列的定义和基本操作

C++中使用STL库中的queue头文件来实现队列操作。但STL库中queue的实现是先进先出的队列（FIFO），而不是优先队列。因此，我们需要使用priority_queue来实现优先队列。

定义优先队列

C++中定义优先队列的语法如下：

priority_queue<元素类型, 容器类型, 比较函数> pq;

其中，元素类型表示队列中元素的类型；容器类型表示队列使用的容器，默认是使用vector；比较函数表示用来判断元素谁更大（优先级更高）的一个函数，可以用户自定义，如果用户没有自定义则默认的比较方法是”小于”（ <）。

基本操作

下表列出了C++ STL中priority_queue支持的主要操作。

C++中的优先队列示例

下面我们通过一些C++实例来说明如何在优先队列中使用C++ STL库。

示例一：使用默认比较器的优先队列

下面我们来看一个简单的示例来创建一个优先队列，用默认的比较函数。我们首先需要包含头文件，如下所示：

#include<bits/stdc++.h>
using namespace std;

我们通过以下代码创建了一个队列，在之后我们用push()方法加入一些元素。

priority_queue<int> pq;
pq.push(7);
pq.push(2);
pq.push(5);
pq.push(1);

我们可以通过top()方法来获取优先队列中的最大值，通过pop()方法来弹出值。

cout << "pq中的最大值：" << pq.top() << endl;
pq.pop();
cout << "取出元素后pq中的最大值：" << pq.top() << endl;

输出结果为：

pq中的最大值：7
取出元素后pq中的最大值：5

示例二：使用自定义比较器的优先队列

在有些情况下，我们可能希望将优先队列的排序方式更改为我们自定义的排序方式。这时我们需要自定义一个比较函数，然后将其作为 priority_queue 的第三个参数传递。

例如，我们想按照元素从大到小的顺序来排列，可以定义一个自定义比较函数：

struct mycomparison {
    bool operator() (const int& a, const int& b) const {
            return a < b;
    }
};

接下来，我们创建一个自定义比较函数的优先队列。

priority_queue<int, vector<int>, mycomparison> pq2;
pq2.push(7);
pq2.push(2);
pq2.push(5);
pq2.push(1);

同样，我们可以通过top()方法来获取优先队列中的最大值，通过pop()方法来弹出值。

cout << "pq2中的最大值：" << pq2.top() << endl;
pq2.pop();
cout << "取出元素后pq2中的最大值：" << pq2.top() << endl;

输出结果为：

pq2中的最大值：1
取出元素后pq2中的最大值：2

值得注意的是，在这个例子中，我们传递了一个自定义比较函数 mycomparison 作为 priority_queue 的第三个参数。这个函数中的 operator() 函数返回一个布尔值，表示两个数字哪一个更大。根据这个函数，我们的优先队列会按照从小到大的顺序排列。

总结

本文简单介绍了C++中优先队列的定义，基本操作以及对优先队列进行自定义排序的方法，并通过示例代码展示了优先队列的使用方法。优先队列是C++中常用的数据结构之一，在程序开发中可以提高代码的效率和准确性。