给定一个数据序列（它可能有重复），一个固定大小的移动窗口，在每次迭代时从数据序列的开始移动窗口，这样（1）最旧的数据元素从窗口中删除，新的数据元素数据元素被推入窗口 (2) 每次移动时求窗口内数据的中位数。
以下帖子没有帮助。
我的想法：
使用 2 个堆来保存中位数。在窗口侧，对第一次迭代窗口中的数据进行排序，最小堆占较大部分，最大堆占较小部分。如果窗口有奇数个数据，则最大堆返回中值，否则两个堆顶部元素的算术平均值为中值。
当新数据被推入窗口时，从其中一个堆中删除最旧的数据，并将新数据与最大和最小堆的顶部进行比较，以便决定将数据放入哪个堆。然后，就像在第一次迭代中一样找到中位数。
但是，如何在堆中找到数据元素是一个问题。堆是二叉树而不是二叉搜索树。
是否可以用 O(n) 或 O(n * lg m) 解决它，其中 m 是窗口大小和空间： O(1) ？
非常感谢任何帮助。
谢谢
O(n*lg m) 很简单：
只需将您的窗口保持为两个std::sets，一个用于下半部分，一个用于上半部分。插入新元素的成本为 O(lg m)，查找和移除旧元素的成本相同。使用您在问题中描述的方法确定中位数需要 O(1)。
当您在序列上滑动窗口时，在每次迭代中，您删除掉出窗口的项目 (O(lg m))，插入新项目 (O(lg m)) 并计算中位数 (O(1)) , 总共有 O(n lg m)。
当然，此解决方案使用空间 O(m)，但我认为不存储窗口内容就无法逃脱。
我几乎完全实现了您在此处描述的算法： http: //ideone.com/8VVEa，并在此处进行了描述： C - Turlach 实现中的滚动中位数
解决“查找最旧”问题的方法是将值保存在循环缓冲区中，因此您始终有一个指向最旧的指针。您存储在堆中的是缓冲区索引。所以空间需求是2M，每次更新是O(lg M)。
我为“C 中的滚动中位数”问题给出了这个答案
我找不到具有 order-statistic 的 c++ 数据结构的现代实现，因此最终在 top coders 链接中实现了这两个想法（匹配编辑：向下滚动到 FloatingMedian）。
第一个想法将数据划分为两个数据结构（堆、多集等），每个插入/删除 O(ln N) 不允许在没有大成本的情况下动态更改分位数。即我们可以有一个滚动的中位数，或者一个滚动的 75%，但不能同时有两者。
第二个想法使用 O(ln N) 的段树进行插入/删除/查询，但更灵活。最好的“N”是数据范围的大小。因此，如果您的滚动中位数具有一百万个项目的窗口，但您的数据与 1..65536 不同，那么每次移动 100 万个滚动窗口只需要 16 次操作！（而且您只需要 65536 * sizeof(counting_type) 个字节，例如 65536*4）。
就在放弃之前，我发现stdlibc++中包含顺序统计树！！！
它们有两个关键操作：
iter = tree.find_by_order(value)
order = tree.order_of_key(value)
请参阅libstdc++ 手册 policy_based_data_structures_test（搜索“拆分和连接”）。
我已经包装了树，以便在支持 c++0x/c++11 样式的部分类型定义的编译器的便利标头中使用：
#if !defined(GNU_ORDER_STATISTIC_SET_H)
#define GNU_ORDER_STATISTIC_SET_H
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// A red-black tree table storing ints and their order
// statistics. Note that since the tree uses
// tree_order_statistics_node_update as its update policy, then it
// includes its methods by_order and order_of_key.
template <typename T>
using t_order_statistic_set = __gnu_pbds::tree<
T,
__gnu_pbds::null_type,
std::less<T>,
__gnu_pbds::rb_tree_tag,
// This policy updates nodes' metadata for order statistics.
__gnu_pbds::tree_order_statistics_node_update>;
#endif //GNU_ORDER_STATISTIC_SET_H
与 hc_ 相同的答案，但不是使用库存 BST，而是使用每个节点都具有该子树中元素计数的版本。这种找到中位数的方法是 O(log(m))。
我附上了我的段树（参见我的另一篇文章），它允许非常有效地查询计数的频率分布。
这实现了以下数据结构：
|-------------------------------|
|---------------|---------------|
|-------|-------|-------|-------|
|---|---|---|---|---|---|---|---|
0 1 2 3 4 5 6 7
每个段将计数项目的数量保持在其涵盖的范围内。我将 2N 段用于 1..N 的值范围。这些被放置在一个展开的向量中，而不是上面形象地显示的树格式。
因此，如果您正在计算一组从 1..65536 变化的整数的滚动中位数，那么您只需要 128kb 来存储它们，并且可以使用 O(ln N) 插入/删除/查询，其中 N = 范围的大小，即 2**16 次操作。
如果数据范围远小于滚动窗口，这是一个巨大的胜利。
#if !defined(SEGMENT_TREE_H)
#define SEGMENT_TREE_H
#include <cassert>
#include <array>
#include <algorithm>
#include <set>
#ifndef NDEBUG
#include <set>
#endif
template<typename COUNTS, unsigned BITS>
class t_segment_tree
{
static const unsigned cnt_elements = (1 << BITS);
static const unsigned cnt_storage = cnt_elements << 1;
std::array<COUNTS, cnt_elements * 2 - 1> counts;
unsigned count;
#ifndef NDEBUG
std::multiset<unsigned> elements;
#endif
public:
//____________________________________________________________________________________
// constructor
//____________________________________________________________________________________
t_segment_tree(): count(0)
{
std::fill_n(counts.begin(), counts.size(), 0);
}
//~t_segment_tree();
//____________________________________________________________________________________
// size
//____________________________________________________________________________________
unsigned size() const { return count; }
//____________________________________________________________________________________
// constructor
//____________________________________________________________________________________
void insert(unsigned x)
{
#ifndef NDEBUG
elements.insert(x);
assert("...............This element is too large for the number of BITs!!..............." && cnt_elements > x);
#endif
unsigned ii = x + cnt_elements;
while (ii)
{
++counts[ii - 1];
ii >>= 1;
}
++count;
}
//____________________________________________________________________________________
// erase
// assumes erase is in the set
//____________________________________________________________________________________
void erase(unsigned x)
{
#ifndef NDEBUG
// if the assertion failed here, it means that x was never "insert"-ed in the first place
assert("...............This element was not 'insert'-ed before it is being 'erase'-ed!!..............." && elements.count(x));
elements.erase(elements.find(x));
#endif
unsigned ii = x + cnt_elements;
while (ii)
{
--counts[ii - 1];
ii >>= 1;
}
--count;
}
//
//____________________________________________________________________________________
// kth element
//____________________________________________________________________________________
unsigned operator[](unsigned k)
{
assert("...............The kth element: k needs to be smaller than the number of elements!!..............." && k < size());
unsigned ii = 1;
while (ii < cnt_storage)
{
if (counts[ii - 1] <= k)
k -= counts[ii++ - 1];
ii <<= 1;
}
return (ii >> 1) - cnt_elements;
}
};
#endif