运行 中位数 window 大小以及长输入
Running Median with window size along with long input
给定一个数据序列（它可能有重复项），固定大小的移动 window，在每次迭代时从数据序列的开头移动 window，这样
(1) 从 window 中删除最旧的数据元素，并将新的数据元素推入 window
(2) 求window内数据在每次移动时的中位数。
此处window大小为7，暂且称它为m。
m = window 尺码
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 个元素的快速排序的帮助下实现了这个东西（三个元素的中位数作为基准）。但这需要很多时间。每次排序都需要。我应该按照提到的那样实施最小和最大堆解决方案 here
Min-Max 堆解决方案中的问题：
当新数据被推入window时，从其中一个堆中移除最旧的数据，并将新数据与 max 的顶部进行比较min heap 以便决定将数据放在哪个堆上。然后，就像在第一次迭代中一样找到中位数。
如何找到从堆中删除最旧的数据，我们如何维护这个。根据给定的示例，第二次 4 是最旧的元素，第三次 6 是最旧的元素。我们如何从堆中删除它。
上述问题的后续问题，如何在堆中找到数据元素是一个问题。堆是二叉树而不是二叉搜索树。
如有任何帮助，我们将不胜感激。
EDIT ：我已经有输入数据，所以没有插入 happening.Only 发生在固定大小队列或 window 不是实际输入序列。
谢谢
对于数据的 运行 中位数（移动 window，其中同时发生插入和删除），使用单个二叉搜索树而不是 min-max 可能更有用移动中的元素堆 window.
二叉搜索树也是一个顺序统计树，存储以每个节点为根的子树的大小。
这棵树将能够在 O(log n) 中进行插入、删除和中值计算。
在上面给出的例子中，每个操作的时间复杂度都是O(log 7)。
除了你的堆DS之外，还持有一个指针（或引用）队列，其中队列中的每个元素都指向代表堆中相关条目的节点。
当您将 window 移动 1 时：
- 出列旧元素
- 按照指针，找到二叉堆中的节点。
- "switch" "last" 节点（最低层中最右边的元素）与您刚刚找到的节点
- 移除新的"last"节点
- 重新堆化
- 使用下一个元素创建二进制堆的新条目
- 将刚刚添加的节点的指针入队
- 重新计算中位数
给定一个数据序列（它可能有重复项），固定大小的移动 window，在每次迭代时从数据序列的开头移动 window，这样 (1) 从 window 中删除最旧的数据元素，并将新的数据元素推入 window (2) 求window内数据在每次移动时的中位数。
此处window大小为7，暂且称它为m。 m = window 尺码 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 个元素的快速排序的帮助下实现了这个东西（三个元素的中位数作为基准）。但这需要很多时间。每次排序都需要。我应该按照提到的那样实施最小和最大堆解决方案 here
Min-Max 堆解决方案中的问题：
当新数据被推入window时，从其中一个堆中移除最旧的数据，并将新数据与 max 的顶部进行比较min heap 以便决定将数据放在哪个堆上。然后，就像在第一次迭代中一样找到中位数。
如何找到从堆中删除最旧的数据，我们如何维护这个。根据给定的示例，第二次 4 是最旧的元素，第三次 6 是最旧的元素。我们如何从堆中删除它。
上述问题的后续问题，如何在堆中找到数据元素是一个问题。堆是二叉树而不是二叉搜索树。
如有任何帮助，我们将不胜感激。
EDIT ：我已经有输入数据，所以没有插入 happening.Only 发生在固定大小队列或 window 不是实际输入序列。
谢谢
对于数据的 运行 中位数（移动 window，其中同时发生插入和删除），使用单个二叉搜索树而不是 min-max 可能更有用移动中的元素堆 window.
二叉搜索树也是一个顺序统计树，存储以每个节点为根的子树的大小。
这棵树将能够在 O(log n) 中进行插入、删除和中值计算。
在上面给出的例子中，每个操作的时间复杂度都是O(log 7)。
除了你的堆DS之外，还持有一个指针（或引用）队列，其中队列中的每个元素都指向代表堆中相关条目的节点。
当您将 window 移动 1 时：
- 出列旧元素
- 按照指针，找到二叉堆中的节点。
- "switch" "last" 节点（最低层中最右边的元素）与您刚刚找到的节点
- 移除新的"last"节点
- 重新堆化
- 使用下一个元素创建二进制堆的新条目
- 将刚刚添加的节点的指针入队
- 重新计算中位数