那些阅读过我之前的问题的人都知道我在理解和实现快速排序和快速选择以及其他一些基本算法方面所做的工作。
快速选择用于计算未排序列表中的第k个最小元素，这个概念也可以用于查找未排序列表中的中位数。
这一次，我需要帮助设计一种有效的技术来计算运行中位数，因为 quickselect 不是一个好的选择，因为它需要在每次列表更改时重新计算。因为 quickselect 每次都必须重新启动，它不能利用之前完成的计算，所以我正在寻找一种不同的算法，它相似(可能)但在运行中位数方面更有效。
最佳答案
streaming median使用两个堆计算。所有小于或等于当前中位数的数都在左堆中，左堆的排列使得最大数在堆的根。所有大于或等于当前中位数的数字都在右堆中，右堆的排列使得最小的数字在堆的根。请注意，等于当前中位数的数字可以在任一堆中。两个堆中的数字计数相差永远不会超过 1。
当进程开始时，两个堆最初是空的。输入序列中的第一个数字被添加到其中一个堆中，不管哪个，并作为第一个流媒体中位数返回。然后将输入序列中的第二个数字添加到另一个堆中，如果右堆的根小于左堆的根，则交换两个堆，并将两个数字的平均值作为第二个流返回中位数。
然后主算法开始。输入序列中的每个后续数字都与当前中值进行比较，如果小于当前中值则添加到左堆，如果大于当前中值则添加到右堆；如果输入数字等于当前中位数，则将其添加到具有较小计数的堆中，或者如果它们具有相同的计数，则任意添加到任一堆中。如果这导致两个堆的计数相差超过 1，则删除较大堆的根并插入较小的堆。然后当前中位数被计算为较大堆的根，如果它们的计数不同，或者两个堆的根的平均值，如果它们的大小相同。
Scheme 和 Python 中的代码可在我的 blog 获得.
关于C++ 高效计算运行中位数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10930732/