# 使用 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; } ```