使用窗口大小与长输入一起运行中间值

Question

给定数据序列(可能有重复的)，一个固定大小的移动窗口，从数据序列开始时在每次迭代时移动窗口，这样(1)从窗口中删除最老的数据元素，并将一个新的数据元素推入窗口(2)在每次移动时找到窗口内数据的中值。

这里的窗口大小是7，我们称它为m. m=窗口大小n=按顺序排列的元素数，可以是1000或10000。

Median for 4, 6, 99, 10, 90, 12, 17,1,21,32  : 12
Median for 6, 99, 10, 90, 12, 17, 1,21,32  : 12
Median for 99, 10, 90, 12, 17, 1, 21,32 : 17
Median for 10, 90, 12, 17, 1, 21, 32 : 17

我每次都使用快速m元素(中间值为3作为枢轴)来实现这个功能。但这需要很长时间。每次分拣都需要。我应该像前面提到的那样实现min和max堆解决方案。

Max堆解决方案中的问题：

当一个新数据被推入窗口时，从堆中删除最老的数据，并将新数据与max和min堆的顶部进行比较，以便决定要放置的数据堆。然后，找到中位数，就像在第一次迭代。

1. 如何从堆中找到删除最老的数据，我们如何维护它。根据第二次给定的例子，4是最古老的元素，第三次6是最古老的元素。我们怎么才能把它从堆里移开。
2. 以上问题的后续问题是，如何在堆中找到数据元素是一个问题。堆是二叉树，而不是二进位搜索树。

任何帮助都将不胜感激。

编辑：我已经有了输入数据，所以没有插入happening.Only发生在固定大小的队列或窗口上，而不是实际的输入序列。

谢谢

Answer 1

除了堆DS之外，还保存一个指针(或引用)队列，其中队列中的每个元素指向表示堆中相关条目的节点。

当你将窗口移动1：

1. 排队旧元素
2. 跟随指针，在二进制堆中找到节点。
3. 用您刚刚找到的节点“切换”“最后”节点(最底层的最右元素)
4. 删除新的“最后”节点
5. 再热化
6. 使用下一个元素创建二进制堆的新条目
7. 将刚才添加的指针排队
8. 重新计算中值

Answer 2

对于正在运行的数据中值(正在进行插入和删除的移动窗口)，对移动窗口中的元素使用单个二进制搜索树而不是min-max堆可能更有用。

二进制搜索树也将是一个顺序统计树，它存储根植于每个节点的子树的大小。

该树将能够在O(log )中执行插入、删除和中值计算。

在上面给出的例子中，每个操作都具有时间复杂度O(log 7)。