在C++中使用示例的优先队列列表

优先队列是一种常见的数据结构，常用于处理具有优先级的元素集合。在C++标准库中，使用priority_queue类可以简便地实现优先队列的功能。下面将为大家介绍如何在C++中使用priority_queue类，以及如何通过示例代码来加深对其的理解。

`priority_queue`类概述

priority_queue类是C++ STL中定义的一个模板类，其具有栈和队列的特性，可以方便地完成元素的插入和删除等操作。priority_queue的特点是元素会按照一定的排序方式自动排序，使得位于队首的元素一定是优先级最高的。C++标准库中提供了一些默认的比较函数，如greater、less等，也允许用户定义自己的比较函数。

priority_queue类的定义如下：

template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > 
class priority_queue;

其中，T为队列中保存元素的类型，Container为存储元素的容器类型，默认为vector<T>，Compare为比较函数的类型，默认为less<typename Container::value_type>。

下面是priority_queue类的基本操作：

push()：将元素插入优先队列
pop()：将队首元素删除
top()：返回队首元素
empty()：判断优先队列是否为空
size()：返回优先队列中元素的数量

示例代码

下面是一个基于priority_queue的示例代码，展示了如何使用优先队列来完成元素的排序。

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

int main()
{
    // 定义int类型的优先队列
    priority_queue<int> q;
    // 插入元素
    q.push(1);
    q.push(3);
    q.push(2);
    // 输出队列元素个数
    cout << "queue size: " << q.size() << endl;
    // 输出队列头元素
    cout << "queue top: " << q.top() << endl;
    // 弹出队列头元素
    q.pop();
    // 输出队列头元素
    cout << "queue top: " << q.top() << endl;
    // 判断队列是否为空
    cout << "queue is empty? " << (q.empty() ? "yes" : "no") << endl;
    // 清空队列
    while (!q.empty())
    {
        q.pop();
    }
    // 输出队列元素个数
    cout << "queue size: " << q.size() << endl;

    return 0;
}

在这个示例代码中，我们定义了一个int类型的优先队列，并通过push()方法向队列中插入了三个元素1、3、2。通过size()方法可以得到队列中元素的个数是3，而top()方法可以得到队首元素是3，因为3是三个元素中最大的。当我们执行了pop()方法后，队首的元素3被弹出，此时队首变成了2，可以通过top()方法来查看队首的元素。最后，我们在一个循环中执行pop()方法，将队列清空，并通过empty()方法来判断队列是否为空，再输出队列元素的个数。

上述代码中的priority_queue类默认使用的是大根堆，因此队列头元素会是最大的元素。如果我们想让队列头元素是最小的元素，可以使用小根堆来实现。具体方法是在定义priority_queue对象时，将Compare参数指定为greater类型的比较函数，如下所示：

// 定义int类型的小根堆
priority_queue<int, vector<int>, greater<int>> q;

这样，我们就可以得到一个小根堆了。下面，让我们通过一个示例来加深对优先队列的理解。

示例

假设我们有一个长度为 $n$ 的整数数组，要求对其进行排序并输出前 $k$ 个最小数。这是一个典型的使用优先队列的问题，可以用下面的步骤来解决：

定义一个priority_queue类，使用小根堆作为比较函数，将整数数组的前 $k$ 个元素插入队列中；
从第 $k+1$ 个元素开始，依次将数组中的元素与优先队列中的队首元素进行比较，如果该元素小于队首元素，则将队首元素弹出并将该元素插入队列中；
遍历完整个数组后，队列中保存的元素即为前 $k$ 个最小数。

下面是使用优先队列来解决这个问题的示例代码：

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

int main()
{
    // 定义int类型的数组和优先队列
    int a[] = { 3, 2, 1, 5, 4, 7, 6, 9, 8, 0 };
    priority_queue<int, vector<int>, greater<int>> q;
    int k = 5;
    // 将前k个元素插入优先队列中
    for (int i = 0; i < k; i++)
    {
        q.push(a[i]);
    }
    // 遍历数组中的元素，插入到优先队列中
    for (int i = k; i < 10; i++)
    {
        if (q.top() > a[i])
        {
            q.pop();
            q.push(a[i]);
        }
    }
    // 输出前k个最小数
    while (!q.empty())
    {
        cout << q.top() << " ";
        q.pop();
    }

    return 0;
}

在这个示例代码中，我们首先定义了一个长度为 $10$ 的整数数组，并定义了一个小根堆优先队列。变量 $k$ 为5，表示我们要输出前5个最小数。

在第8至12行，我们将整数数组的前 $k$ 个元素插入了优先队列中。从第13行开始，我们遍历数组中的元素，即从第6个元素开始，依次与优先队列中的队首元素进行比较。如果该元素小于队首元素，则将队首元素弹出并将该元素插入队列中，即实现了维护前 $k$ 个最小数的功能。

最后，在第22至26行，我们在循环中输出了前 $k$ 个最小数。

结论

priority_queue是C++标准库中一个非常有用的类，用于实现优先队列功能。通过使用priority_queue类，我们可以方便地排序和处理具有优先级的元素集合。同时，由于其底层通常采用堆的数据结构实现，因此在操作复杂度上也有较好的表现。在实际编程中，我们可以结合具体问题需求，使用不同的比较函数和元素类型来实现不同的应用。