中位數為整數流（運行整數） · GeeksForGeeks 中文系列教程

# 中位數為整數流（運行整數） > 原文： [https://www.geeksforgeeks.org/median-of-stream-of-integers-running-integers/](https://www.geeksforgeeks.org/median-of-stream-of-integers-running-integers/) 假定從數據流中讀取整數。查找所讀元素的中位數，以便高效地進行閱讀。為簡單起見，假設沒有重復項。例如，讓我們考慮流 5、15、1、3… ``` After reading 1st element of stream - 5 -> median - 5 After reading 2nd element of stream - 5, 15 -> median - 10 After reading 3rd element of stream - 5, 15, 1 -> median - 5 After reading 4th element of stream - 5, 15, 1, 3 -> median - 4, so on... ``` 明確地說，當輸入大小為奇數時，我們采用排序數據的中間元素。如果輸入大小為偶數，則選擇排序流中中間兩個元素的平均值。請注意，輸出是到目前為止從流中讀取的整數的*有效中位數*。這種算法稱為在線算法。在處理完第 *i* 個元素之后，可以保證 *i* 元素輸出的任何算法都稱為 ***在線算法*** 。讓我們討論上述問題的三種解決方案。 **方法 1**：插入排序如果我們可以對顯示的數據進行排序，則可以輕松地找到中值元素。 *插入排序*是一種在線算法，用于對到目前為止出現的數據進行排序。在任何排序實例中，例如，在對第*個*個元素進行排序之后，將對數組的第一個*第*個元素進行排序。在此之前，插入排序并不依賴將來的數據來對輸入的數據進行排序。換句話說，插入排序考慮到插入下一個元素時到目前為止已排序的數據。這是使其成為在線算法的插入排序的關鍵部分。但是，插入排序需要 `O(n^2)`時間來對 *n* 個元素進行排序。也許我們可以對*插入排序*使用*二分搜索*來查找`O(log n)`時間中下一個元素的位置。但是，我們無法在`O(log n)`時間內進行數據移動。無論實現的效率如何，在插入排序的情況下都需要多項式時間。有興趣的讀者可以嘗試方法 1 的實現。 **方法 2**：增強的自平衡二分搜索樹（AVL，RB 等）在 BST 的每個節點上，維護以該節點為根的子樹中的元素數量。我們可以將節點用作簡單二叉樹的根，其左子節點是具有小于根的元素的自平衡 BST，右子節點是具有大于根的元素的自平衡 BST。根元素始終保持*有效中位數*。如果左右子樹包含相同數量的元素，則根節點將保存左右子樹根數據的平均值。否則，root 包含與具有更多元素的子樹的根相同的數據。處理完傳入元素后，左右子樹（BST）相差最大 1。自平衡 BST 在管理 BST 的平衡因子方面成本很高。但是，它們提供了我們不需要的排序數據。我們只需要中位數。下一種方法利用堆來跟蹤中位數。 **方法 3**：堆與上述方法 2 中的平衡 BST 相似，我們可以在左側使用最大堆表示小于*有效中位數*的元素，在右側使用最小堆表示大于*的元素有效中位數*。處理傳入的元素后，堆中的元素數量最大相差 1 個元素。當兩個堆包含相同數量的元素時，我們選擇堆根數據的平均值作為*有效中位數*。當堆不平衡時，我們從包含更多元素的堆根中選擇*有效中位數*。下面給出上述方法的實現。有關構建這些堆的算法，請閱讀突出顯示的代碼。 ``` #include <iostream> using namespace std; // Heap capacity #define MAX_HEAP_SIZE (128) #define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0]) //// Utility functions // exchange a and b inline void Exch(int &a, int &b) { ????int aux = a; ????a = b; ????b = aux; } // Greater and Smaller are used as comparators bool Greater(int a, int b) { ????return a > b; } bool Smaller(int a, int b) { ????return a < b; } int Average(int a, int b) { ????return (a + b) / 2; } // Signum function // = 0? if a == b? - heaps are balanced // = -1 if a < b?? - left contains less elements than right // = 1? if a > b?? - left contains more elements than right int Signum(int a, int b) { ????if( a == b ) ????????return 0; ????return a < b ? -1 : 1; } // Heap implementation // The functionality is embedded into // Heap abstract class to avoid code duplication class Heap { public: ????// Initializes heap array and comparator required ????// in heapification ????Heap(int *b, bool (*c)(int, int)) : A(b), comp(c) ????{ ????????heapSize = -1; ????} ????// Frees up dynamic memory ????virtual ~Heap() ????{ ????????if( A ) ????????{ ????????????delete[] A; ????????} ????} ????// We need only these four interfaces of Heap ADT ????virtual bool Insert(int e) = 0; ????virtual int? GetTop() = 0; ????virtual int? ExtractTop() = 0; ????virtual int? GetCount() = 0; protected: ????// We are also using location 0 of array ????int left(int i) ????{ ????????return 2 * i + 1; ????} ????int right(int i) ????{ ????????return 2 * (i + 1); ????} ????int parent(int i) ????{ ????????if( i <= 0 ) ????????{ ????????????return -1; ????????} ????????return (i - 1)/2; ????} ????// Heap array ????int?? *A; ????// Comparator ????bool? (*comp)(int, int); ????// Heap size ????int?? heapSize; ????// Returns top element of heap data structure ????int top(void) ????{ ????????int max = -1; ????????if( heapSize >= 0 ) ????????{ ????????????max = A[0]; ????????} ????????return max; ????} ????// Returns number of elements in heap ????int count() ????{ ????????return heapSize + 1; ????} ????// Heapification ????// Note that, for the current median tracing problem ????// we need to heapify only towards root, always ????void heapify(int i) ????{ ????????int p = parent(i); ????????// comp - differentiate MaxHeap and MinHeap ????????// percolates up ????????if( p >= 0 && comp(A[i], A[p]) ) ????????{ ????????????Exch(A[i], A[p]); ????????????heapify(p); ????????} ????} ????// Deletes root of heap ????int deleteTop() ????{ ????????int del = -1; ????????if( heapSize > -1) ????????{ ????????????del = A[0]; ????????????Exch(A[0], A[heapSize]); ????????????heapSize--; ????????????heapify(parent(heapSize+1)); ????????} ????????return del; ????} ????// Helper to insert key into Heap ????bool insertHelper(int key) ????{ ????????bool ret = false; ????????if( heapSize < MAX_HEAP_SIZE ) ????????{ ????????????ret = true; ????????????heapSize++; ????????????A[heapSize] = key; ????????????heapify(heapSize); ????????} ????????return ret; ????} }; // Specilization of Heap to define MaxHeap class MaxHeap : public Heap { private: public: ????MaxHeap() : Heap(new int[MAX_HEAP_SIZE], &Greater)? {? } ????~MaxHeap()? { } ????// Wrapper to return root of Max Heap ????int GetTop() ????{ ????????return top(); ????} ????// Wrapper to delete and return root of Max Heap ????int ExtractTop() ????{ ????????return deleteTop(); ????} ????// Wrapper to return # elements of Max Heap ????int? GetCount() ????{ ????????return count(); ????} ????// Wrapper to insert into Max Heap ????bool Insert(int key) ????{ ????????return insertHelper(key); ????} }; // Specilization of Heap to define MinHeap class MinHeap : public Heap { private: public: ????MinHeap() : Heap(new int[MAX_HEAP_SIZE], &Smaller) { } ????~MinHeap() { } ????// Wrapper to return root of Min Heap ????int GetTop() ????{ ????????return top(); ????} ????// Wrapper to delete and return root of Min Heap ????int ExtractTop() ????{ ????????return deleteTop(); ????} ????// Wrapper to return # elements of Min Heap ????int? GetCount() ????{ ????????return count(); ????} ????// Wrapper to insert into Min Heap ????bool Insert(int key) ????{ ????????return insertHelper(key); ????} }; // Function implementing algorithm to find median so far. int getMedian(int e, int &m, Heap &l, Heap &r) { ????// Are heaps balanced? If yes, sig will be 0 ????int sig = Signum(l.GetCount(), r.GetCount()); ????switch(sig) ????{ ????case 1: // There are more elements in left (max) heap ????????if( e < m ) // current element fits in left (max) heap ????????{ ????????????// Remore top element from left heap and ????????????// insert into right heap ????????????r.Insert(l.ExtractTop()); ????????????// current element fits in left (max) heap ????????????l.Insert(e); ????????} ????????else ????????{ ????????????// current element fits in right (min) heap ????????????r.Insert(e); ????????} ????????// Both heaps are balanced ????????m = Average(l.GetTop(), r.GetTop()); ????????break; ????case 0: // The left and right heaps contain same number of elements ????????if( e < m ) // current element fits in left (max) heap ????????{ ????????????l.Insert(e); ????????????m = l.GetTop(); ????????} ????????else ????????{ ????????????// current element fits in right (min) heap ????????????r.Insert(e); ????????????m = r.GetTop(); ????????} ????????break; ????case -1: // There are more elements in right (min) heap ????????if( e < m ) // current element fits in left (max) heap ????????{ ????????????l.Insert(e); ????????} ????????else ????????{ ????????????// Remove top element from right heap and ????????????// insert into left heap ????????????l.Insert(r.ExtractTop()); ????????????// current element fits in right (min) heap ????????????r.Insert(e); ????????} ????????// Both heaps are balanced ????????m = Average(l.GetTop(), r.GetTop()); ????????break; ????} ????// No need to return, m already updated ????return m; } void printMedian(int A[], int size) { ????int m = 0; // effective median ????Heap *left? = new MaxHeap(); ????Heap *right = new MinHeap(); ????for(int i = 0; i < size; i++) ????{ ????????m = getMedian(A[i], m, *left, *right); ????????cout << m << endl; ????} ????// C++ more flexible, ensure no leaks ????delete left; ????delete right; } // Driver code int main() { ????int A[] = {5, 15, 1, 3, 2, 8, 7, 9, 10, 6, 11, 4}; ????int size = ARRAY_SIZE(A); ????// In lieu of A, we can also use data read from a stream ????printMedian(A, size); ????return 0; } ``` **時間復雜度**：如果我們省略讀取流的方式，則中位數查找的復雜度為 ***`O(N log N)`*** ，因為我們需要讀取流，以及由于堆的插入/刪除。乍一看，上面的代碼可能看起來很復雜。如果仔細閱讀代碼，這是簡單的算法。 [**使用 STL**](https://www.geeksforgeeks.org/median-of-stream-of-running-integers-using-stl/) 的運行整數流的中位數 - [**Venki**](http://www.linkedin.com/in/ramanawithu) 。如果發現任何不正確的地方，或者想分享有關上述主題的更多信息，請寫評論。