algorithm - 动态更新数组的第 k 阶统计量

Question

我想跟踪一个不断增长或缩小的数组的第 k 个最大元素(k 是固定的)。我可以使用哪种数据结构来实现最佳时间复杂度？

当数组仅增长时(输入以流的形式传入)，最小堆可实现最佳复杂度。

当k不固定时，可以在这里找到使用最小堆和最大堆的解决方案:Find running median from a stream of integers

当 k 固定时，使用两个堆是否也是最优的？

Answer 1

如果数组不断增长，您将向 minHeap 添加一个元素，当它达到 k + 1 时，您删除顶部，因此堆上有前 k 个元素，最小元素位于根。

我相信如果您使用 maxHeap，您也可以达到同样的效果。当您达到 k + 1 个元素时删除顶部后，您将拥有相同的顶部 k 个元素，但最大值将位于根部。

现在当数组减少时，在每次删除时查看被删除的元素是否大于 maxHeap 的 peek 并且该数组大小仍然大于或等于 k，那么您不需要做任何事情。

如果数组大小减小到 k 以下，那么第 k 个最大的将变得无效，然后随着数组的减小，您将一个一个地移除 maxHeap 顶部。

这是困难的部分:

但是当被移除的元素小于 maxHeap 的 peek 并且数组大小仍然 >= k 将元素添加到 maxHeap，如果该元素已经存在于堆中，则大小没有变化表明该元素是在堆里。删除该元素并添加数组中的最后一个元素。