在C ++ STL中的priority_queue :: top()

在C ++ STL中，priority_queue是一个非常实用的数据结构，用于自动排序。它是一个队列，其中每个元素都有其优先级，该队列按照优先级排序，优先级最高的元素总是在队列头部。priority_queue的操作主要包括压入元素（push()）、移除元素（pop()）和访问元素（top()）。本篇文章将重点介绍priority_queue::top()函数的用法及示例代码。

`priority_queue::top()`的定义和用法

在C ++ STL中，priority_queue::top()函数用于访问priority_queue的顶部元素，该函数返回值为队列的顶部元素的引用。

const T& top() const;

其中，T是数据类型，表示队列中存储元素的数据类型，常用的数据类型有int、double、string等。

top()函数是一个常量成员函数，因此不会修改队列的内容。如果队列为空，则访问top()函数将导致未定义的行为。

下面是一个使用top()函数的示例程序：

#include <queue>
#include <iostream>

using namespace std;

int main()
{
    priority_queue<int> mypq;
    mypq.push(30);
    mypq.push(100);
    mypq.push(25);
    mypq.push(40);

    cout << "队列的头部元素为：" << mypq.top() << endl;

    return 0;
}

代码输出将为：

队列的头部元素为：100

在上面的示例程序中，我们先创建了一个整数类型的priority_queue对象mypq，然后向其压入了4个元素。最后，我们使用top()函数输出了该队列的头部元素，即优先级最高的元素。

`priority_queue::top()`的案例分析

我们可以通过实际案例来理解priority_queue::top()函数的用法。下面，我们来看一个找出一组数的中位数的案例。假设我们有一些数字，需要找出其中的中位数，即将这些数字排序后位于中间位置的数字。

我们可以使用两个priority_queue对象来实现这个功能，一个存放较小的数字，一个存放较大的数字。将所有数字压入两个队列，保持这两个队列的元素个数相等或最多相差1，即每个数字至少同时出现在一个队列中。这样，如果队列元素个数为偶数，取两个队列的头部元素的平均值即为中位数，如果队列元素个数为奇数，取元素个数较多的队列的头部元素即为中位数。

下面是完整的示例代码：

#include <iostream>
#include <queue>

using namespace std;

double GetMedian(priority_queue<int, vector<int>, less<int> >& left,
              priority_queue<int, vector<int>, greater<int> >& right)
{
    int left_size = left.size();
    int right_size = right.size();
    if (left_size == right_size)
    {
        return (double)(left.top() + right.top()) / 2;
    }
    else
    {
        return left_size > right_size ? left.top() : right.top();
    }
}

void Insert(priority_queue<int, vector<int>, less<int> >& left,
            priority_queue<int, vector<int>, greater<int> >& right,
            int num)
{
    if (left.empty() || num <= left.top())
    {
        left.push(num);
    }
    else
    {
        right.push(num);
    }

    if (left.size() == right.size() + 2)
    {
        right.push(left.top());
        left.pop();
    }
    else if (right.size() == left.size() + 1)
    {
        left.push(right.top());
        right.pop();
    }

    return;
}

int main()
{
    priority_queue<int, vector<int>, less<int> > left_queue;  // 存放较小的数字（最大堆）
    priority_queue<int, vector<int>, greater<int> > right_queue;  // 存放较大的数字（最小堆）
    int num;
    cout << "请输入数字（以任意非数字字符结束）：" << endl;
    while (cin >> num)  // 读入数字，直到遇到非数字字符
    {
        Insert(left_queue, right_queue, num);
        double median = GetMedian(left_queue, right_queue);
        cout << "当前中位数为：" << median << endl;
    }

    return 0;
}

在上面的程序中，我们使用了两个priority_queue对象，其中一个是最大堆（较小的数字，即从大到小排序），另一个是最小堆（较大的数字，即从小到大排序）。Insert()函数用于将每个数字插入到相应的队列中，并根据队列元素个数的比较，决定是否需要移动元素。GetMedian()函数用于计算中位数。

通过以上程序，我们可以输入一组数字，程序会不断计算出当前输入数字的中位数，并输出中位数的值。下面是程序输出的一部分内容：

请输入数字（以任意非数字字符结束）：
10
当前中位数为：10
20
当前中位数为：15
30
当前中位数为：20
40
当前中位数为：25
50
当前中位数为：30
a

可以看到，我们成功地实现了基于priority_queue的中位数算法。

结论

本篇文章介绍了C ++ STL中的priority_queue::top()函数的定义、用法和示例代码，并重点讲解了如何通过priority_queue对象计算一组数字的中位数。priority_queue是一个重要的数据结构，它在各种算法、数值计算和机器学习等领域都有广泛的应用，值得我们深入学习和掌握。