数据流中最近K个元素的中位数算法：复杂度与优化问询

问题描述 #

给定奇数K，输入包含N个数字的数据流。每读取一个数字（前K-1个除外），需要输出最近K个数字的中位数。

我的实现方案 #

我采用双堆（MaxHeap大顶堆和MinHeap小顶堆）实现，为堆扩展了remove_element函数：该函数遍历堆查找目标元素，删除后重新平衡堆结构，时间复杂度为O(K+logK)。整体解法逻辑为：遍历数据流，将新元素加入堆中，同时删除滑动窗口外的旧元素（即窗口滑动后被移出的最早元素），估算整体时间复杂度为O(N*K)。

待解疑问 #

• 上述算法的时间复杂度估算是否正确？
• 有没有办法对该算法进行提速优化？
• 若当前算法已达最优，该如何证明其最优性？我个人的思路是：如果O(N*K)的时间复杂度估算正确，可以基于“每次输出中位数必须检查全部K个元素”的逻辑来完成最优性证明。

内容的提问来源于stack exchange，提问作者some_guy256