# 流中的第 K 個最大元素 > 原文： [https://www.geeksforgeeks.org/kth-largest-element-in-a-stream/](https://www.geeksforgeeks.org/kth-largest-element-in-a-stream/) 給定無限的整數流，請在任何時間點找到第`k`個最大元素。 例： ``` Input: stream[] = {10, 20, 11, 70, 50, 40, 100, 5, ...} k = 3 Output: {_, _, 10, 11, 20, 40, 50, 50, ...} ``` 允許的額外空間為`O(k)`。 在以下文章中，我們討論了在數組中找到第`k`個最大元素的不同方法。 [未排序數組中第`K`個最小/最大元素| 集合 1](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/) [未排序數組中第`K`個最小/最大元素| 組 2（預期線性時間）](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-2-expected-linear-time/) [未排序數組中第`K`個最小/最大元素| 第 3 組（最差情況的線性時間）](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/) 在這里，我們有一個流而不是整個數組，并且只允許存儲`k`個元素。 **簡單解決方案**是保持大小為`k`的數組。 想法是保持數組排序，以便在`O(1)`時間內找到第`k`個最大元素（如果數組按升序排序，我們只需要返回數組的第一個元素） 如何處理 流的新元素？ 對于流中的每個新元素，請檢查新元素是否小于當前的第`k`個最大元素。 如果是，則忽略它。 如果否，則從數組中刪除最小的元素，并按排序順序插入新元素。 處理新元素的時間復雜度為`O(k)`。 **更好的解決方案**是使用大小為`k`的自平衡二分搜索樹。 可以在`O(Logk)`時間中找到第`k`個最大元素。 如何處理流的新元素？ 對于流中的每個新元素，請檢查新元素是否小于當前的第`k`個最大元素。 如果是，則忽略它。 如果否，則從樹中刪除最小的元素并插入新元素。 處理新元素的時間復雜度為`O(Logk)`。 一種有效的**解決方案**是使用大小為`k`的最小堆存儲流的`k`個最大元素。 第`k`個最大元素始終位于根，可以在`O(1)`時間找到。 如何處理流的新元素？ 將新元素與堆根進行比較。 如果新元素較小，則將其忽略。 否則，將`root`替換為新元素，然后調用建堆作為修改后的堆的根。 找到第`k`個最大元素的時間復雜度是`O(Logk)`。 ``` // A C++ program to find k'th smallest element in a stream #include<iostream> #include<climits> using namespace std; // Prototype of a utility function to swap two integers void swap(int *x, int *y); // A class for Min Heap class MinHeap { ????int *harr; // pointer to array of elements in heap ????int capacity; // maximum possible size of min heap ????int heap_size; // Current number of elements in min heap public: ????MinHeap(int a[], int size); // Constructor ????void buildHeap(); ????void MinHeapify(int i);? //To minheapify subtree rooted with index i ????int parent(int i)? { return (i-1)/2;? } ????int left(int i)??? { return (2*i + 1);? } ????int right(int i)?? { return (2*i + 2);? } ????int extractMin();? // extracts root (minimum) element ????int getMin()?????? {? return harr[0]; } ????// to replace root with new node x and heapify() new root ????void replaceMin(int x) { harr[0] = x; MinHeapify(0); } }; MinHeap::MinHeap(int a[], int size) { ????heap_size = size; ????harr = a;? // store address of array } void MinHeap::buildHeap() { ????int i = (heap_size - 1)/2; ????while (i >= 0) ????{ ????????MinHeapify(i); ????????i--; ????} } // Method to remove minimum element (or root) from min heap int MinHeap::extractMin() { ????if (heap_size == 0) ????????return INT_MAX; ????// Store the minimum vakue. ????int root = harr[0]; ????// If there are more than 1 items, move the last item to root ????// and call heapify. ????if (heap_size > 1) ????{ ????????harr[0] = harr[heap_size-1]; ????????MinHeapify(0); ????} ????heap_size--; ????return root; } // A recursive method to heapify a subtree with root at given index // This method assumes that the subtrees are already heapified void MinHeap::MinHeapify(int i) { ????int l = left(i); ????int r = right(i); ????int smallest = i; ????if (l < heap_size && harr[l] < harr[i]) ????????smallest = l; ????if (r < heap_size && harr[r] < harr[smallest]) ????????smallest = r; ????if (smallest != i) ????{ ????????swap(&harr[i], &harr[smallest]); ????????MinHeapify(smallest); ????} } // A utility function to swap two elements void swap(int *x, int *y) { ????int temp = *x; ????*x = *y; ????*y = temp; } // Function to return k'th largest element from input stream void kthLargest(int k) { ????// count is total no. of elements in stream seen so far ????int count = 0, x;? // x is for new element ????// Create a min heap of size k ????int *arr = new int[k]; ????MinHeap mh(arr, k); ????while (1) ????{ ????????// Take next element from stream ????????cout << "Enter next element of stream "; ????????cin >> x; ????????// Nothing much to do for first k-1 elements ????????if (count < k-1) ????????{ ????????????arr[count] = x; ????????????count++; ????????} ????????else ????????{ ??????????// If this is k'th element, then store it ??????????// and build the heap created above ??????????if (count == k-1) ??????????{ ??????????????arr[count] = x; ??????????????mh.buildHeap(); ??????????} ??????????else ??????????{ ???????????????// If next element is greater than? ???????????????// k'th largest, then replace the root ???????????????if (x > mh.getMin()) ??????????????????mh.replaceMin(x); // replaceMin calls? ????????????????????????????????????// heapify() ??????????} ??????????// Root of heap is k'th largest element ??????????cout << "K'th largest element is " ???????????????<< mh.getMin() << endl; ??????????count++; ????????} ????} } // Driver program to test above methods int main() { ????int k = 3; ????cout << "K is " << k << endl; ????kthLargest(k); ????return 0; } ``` 輸出量 ``` K is 3 Enter next element of stream 23 Enter next element of stream 10 Enter next element of stream 15 K'th largest element is 10 Enter next element of stream 70 K'th largest element is 15 Enter next element of stream 5 K'th largest element is 15 Enter next element of stream 80 K'th largest element is 23 Enter next element of stream 100 K'th largest element is 70 Enter next element of stream CTRL + C pressed ```