使用 STL 的运行整数流的中位数 · GeeksForGeeks 中文系列教程

# 使用 STL 的运行整数流的中位数 > 原文： [https://www.geeksforgeeks.org/median-of-stream-of-running-integers-using-stl/](https://www.geeksforgeeks.org/median-of-stream-of-running-integers-using-stl/) 假定正在从数据流中读取整数。查找从第一个整数到最后一个整数到目前为止读取的所有元素的中值。这也称为运行整数中位数。数据流可以是任何数据源，例如：文件，整数数组，输入流等。 **什么是中位数？** 中位数可以定义为数据集中将数据样本的上半部分与下半部分分开的元素。换句话说，我们可以得到中位数元素，因为当输入大小为奇数时，我们采用排序数据的中间元素。如果输入大小为偶数，则选择排序流中中间两个元素的平均值。 **示例**： ``` Input: 5 10 15 Output: 5 7.5 10 ``` **说明**：给定输入流为整数`[5, 10, 15]`的数组。现在，我们将一一读取整数并相应地打印中位数。因此，在读取第一个元素 5 之后，中间值为 5。在读取 10 之后，中间值为 7.5。在读取 15 之后，中间值为 10。这个想法是使用最大堆和最小堆来存储上半部分和下半部分的元素。可以使用 C++ STL 中的 [priority_queue](https://www.geeksforgeeks.org/priority-queue-in-cpp-stl/) 来实现最大堆和最小堆。以下是解决此问题的分步算法。 **算法**： 1. 创建两个堆。在任何时间点，一个最大堆用于维护较低部分的元素，而一个最小堆用于维护较高一半的元素。 2. 将中位数的初始值设为 0。 3. 对于每个新读取的元素，请将其插入最大堆或最小堆，并根据以下条件计算中位数： * 如果最大堆的大小大于最小堆的大小，并且该元素小于先前的中位数，则从最大堆中弹出顶部元素，然后插入到最小堆中，然后将新元素插入到最大堆中，否则将新元素插入到最小堆中。计算新的中位数，作为最大和最小堆元素顶部的平均值。 * 如果最大堆的大小小于最小堆的大小，并且该元素大于先前的中位数，则从最小堆中弹出顶部元素，然后插入到最大堆中，然后将新元素插入到最小堆中，否则将新元素插入到最大堆中。计算新的中位数，作为最大和最小堆元素顶部的平均值。 * 如果两个堆的大小相同。然后检查当前电流是否小于先前的中位数。如果当前元素小于先前的中值，则将其插入最大堆，新的中值将等于最大堆的顶部元素。如果当前元素大于先前的中值，则将其插入最小堆，新的中值将等于最小堆的顶部元素。下面是上述方法的实现： ## C++ ```cpp // C++ program to find med in // stream of running integers #include<bits/stdc++.h> using namespace std; // function to calculate med of stream void printMedians(double arr[], int n) { // max heap to store the smaller half elements priority_queue<double> s; // min heap to store the greater half elements priority_queue<double,vector<double>,greater<double> > g; double med = arr[0]; s.push(arr[0]); cout << med << endl; // reading elements of stream one by one /* At any time we try to make heaps balanced and their sizes differ by at-most 1\. If heaps are balanced,then we declare median as average of min_heap_right.top() and max_heap_left.top() If heaps are unbalanced,then median is defined as the top element of heap of larger size */ for (int i=1; i < n; i++) { double x = arr[i]; // case1(left side heap has more elements) if (s.size() > g.size()) { if (x < med) { g.push(s.top()); s.pop(); s.push(x); } else g.push(x); med = (s.top() + g.top())/2.0; } // case2(both heaps are balanced) else if (s.size()==g.size()) { if (x < med) { s.push(x); med = (double)s.top(); } else { g.push(x); med = (double)g.top(); } } // case3(right side heap has more elements) else { if (x > med) { s.push(g.top()); g.pop(); g.push(x); } else s.push(x); med = (s.top() + g.top())/2.0; } cout << med << endl; } } // Driver program to test above functions int main() { // stream of integers double arr[] = {5, 15, 10, 20, 3}; int n = sizeof(arr)/sizeof(arr[0]); printMedians(arr, n); return 0; } ```