C++程序在数据流中查找第k大元素

给定一个无限的整数流，查找任何时刻的第k大元素。

例子：

输入：

stream[] = {10, 20, 11, 70, 50, 40, 100, 5, …}

k = 3

输出： {_, _, 10, 11, 20, 40, 50, 50, …}

允许的额外空间为O(k)。

一个 简单的解决方案 是保持大小为k的数组。想法是让数组排序，以便可以在O(1)时间内找到第k大的元素（如果数组按增量顺序排序，我们只需返回数组的第一个元素）。

如何处理流的新元素？

对于流中的每个新元素，请检查新元素是否小于当前的第k大元素。如果是，则忽略它。否则，从数组中删除最小元素并以排序顺序插入新元素。处理新元素的时间复杂度为O(k)。

一个 更好的解决方案 是使用大小为k的自平衡二叉搜索树。可以在O(Logk)时间内找到第k大的元素。
如何处理流的新元素？

对于流中的每个新元素，请检查新元素是否小于当前的第k大元素。如果是，则忽略它。否则，从树中删除最小元素并插入新元素。处理新元素的时间复杂度为O(Logk)。

一个 高效的解决方案 是使用大小为k的小根堆来存储流的k个最大元素。第k大的元素始终位于根处，并且可以在O(1)时间内找到它。

如何处理流的新元素？

将新元素与堆的根进行比较。如果新元素较小，则忽略它。否则，将根替换为新元素并对修改后的堆的根进行堆化调用。找到第k大的元素的时间复杂度为O(Logk)。

// 在流中找到第k小的元素的C++程序
#include <climits>
#include <iostream>
using namespace std;
 
// 交换两个整数的实用函数的原型
void swap(int* x, int* y);
 
// MinHeap类
class MinHeap {
    int* harr; // 指向堆中元素数组的指针
    int capacity; // 最小堆的可能最大尺寸
    int heap_size; // 目前最小堆中的元素数量
public:
    MinHeap(int a[], int size); //构造函数
    void buildHeap();
    void MinHeapify(
        int i); // 对以索引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(); // 抽取根节点（最小）元素
    int getMin() { return harr[0]; }
 
    // 用新节点x替换根节点并堆化新节点
    void replaceMin(int x)
    {
        harr[0] = x;
        MinHeapify(0);
    }
};
 
MinHeap::MinHeap(int a[], int size)
{
    heap_size = size;
    harr = a; // 存储数组的地址
}
 
void MinHeap::buildHeap()
{
    int i = (heap_size - 1) / 2;
    while (i >= 0) {
        MinHeapify(i);
        i--;
    }
}
 
// 从最小堆中删除最小的元素（或根）
int MinHeap::extractMin()
{
    if (heap_size == 0)
        return INT_MAX;
 
    // 存储最小值
    int root = harr[0];
 
    // 如果有多于1个元素，
    // 将最后一个元素移到根并调用heapify
    if (heap_size > 1) {
        harr[0] = harr[heap_size - 1];
        MinHeapify(0);
    }
    heap_size--;
 
    return root;
}
 
// 对以指定索引为根的子树进行堆化的递归方法，假设子树已经堆化
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(↔[i], ↔[smallest]);
        MinHeapify(smallest);
    }
}
 
// 交换两个元素的实用函数
void swap(int* x, int* y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}
 
// 返回输入数据流中第k大的元素的函数
void kthLargest(int k)
{
    // count是迄今为止在流中看到的元素的总数
    int count = 0, x; // x是新元素
 
    // 创建大小为k的最小堆
    int* arr = new int[k];
    MinHeap mh(arr, k);
 
    while (1) {
        // 从流中获取下一个元素
        cout << "输入下一个流元素 ";
        cin >> x;
 
        // 对于前k-1个元素，没有什么要做的
        if (count < k - 1) {
            arr[count] = x;
            count++;
        }
 
        else {
            // 如果这是第k个元素，则将其存储起来，
            // 并建立上面创建的堆。
            if (count == k - 1) {
                arr[count] = x;
                mh.buildHeap();
            }
 
            else {
                // 如果下一个元素比第k大的元素大，则替换根
                if (x > mh.getMin())
                    mh.replaceMin(x); // replaceMin调用heapify()
            }
 
            // 堆根是第k大元素
            cout << "第k大的元素是 "
                 << mh.getMin() << endl;
            count++;
        }
    }
}
 
// 测试以上方法的驱动程序
int main()
{
    int k = 3;
    cout << "k是 " << k << endl;
    kthLargest(k);
    return 0;
}

输出：

K是3
输入流的下一个元素23
输入流的下一个元素10
输入流的下一个元素15
第k大的元素是10
输入流的下一个元素70
第k大的元素是15
输入流的下一个元素5
第k大的元素是15
输入流的下一个元素80
第k大的元素是23
输入流的下一个元素100
第k大的元素是70
输入流的下一个元素
按了CTRL + C

时间复杂度： O（N * log K）

使用优先队列实现：

//上面的方法的 C++ 实现
#include <bits/stdc++.h>
using namespace std;
 
vector<int> kthLargest(int k, int arr[], int n)
{
    vector<int> ans(n);
 
    //使用优先队列创建最小堆
    priority_queue<int, vector<int>, greater<int> > pq;
 
    //遍历每个元素
    for (int i = 0; i < n; i++) {
        //如果优先队列的大小小于 k
        if (pq.size() < k)
            pq.push(arr[i]);
        else {
            if (arr[i] > pq.top()) {
                pq.pop();
                pq.push(arr[i]);
            }
        }
 
        //如果数量小于 k
        if (pq.size() < k)
            ans[i] = -1;
        else
            ans[i] = pq.top();
    }
 
    return ans;
}
 
//主函数
int main()
{
    int n = 6;
    int arr[n] = { 1, 2, 3, 4, 5, 6 };
    int k = 4;
   
    //函数调用
    vector<int> v = kthLargest(k, arr, n);
    for (auto it : v)
        cout << it << " ";
    return 0;
}