那些阅读过我以前的问题的人都知道我在理解和实现quicksort和quickselect以及其他一些基本算法方面的工作。
快速选择用于计算未排序列表中的第k个最小元素，并且此概念还可以用于查找未排序列表中的中位数。
这次，我需要帮助设计一种有效的技术来计算 运行中位数 ，因为quickselect并不是一个好的选择，因为每次列表更改时都需要重新计算。由于quickselect每次都必须重新启动，因此无法利用以前完成的计算，因此我正在寻找一种类似的算法（可能），但在运行中位数方面效率更高。
该流中位数是用两个堆计算。所有小于或等于当前中位数的数字都在左堆中，左堆的排列方式是使最大数位于堆的根部。所有大于或等于当前中位数的数字都在正确的堆中，该堆的排列方式是使最小数在堆的根部。请注意，等于当前中位数的数字可以位于任一堆中。两个堆中的数字计数相差不超过1。
当过程开始时，两个堆最初是空的。输入序列中的第一个数字被添加到一个堆中，这无关紧要，并作为第一个流中位数返回。然后，将输入序列中的第二个数字添加到另一个堆中，如果右堆的根小于左堆的根，则将两个堆交换，并且将两个数的平均值作为第二个流返回中位数。
然后主要算法开始。将输入序列中的每个后续数字与当前中位数进行比较，如果小于当前中位数，则将其添加到左堆中；如果大于当前中位数，则将其添加到右堆中；如果输入数字等于当前的中位数，则将其添加到计数较小的堆中，或者将其添加到计数相同的任意堆中。如果这导致两个堆的计数相差大于1，则将删除较大堆的根并将其插入较小堆中。然后，如果计数不同，则将当前中位数计算为较大堆的根，如果大小相同，则将其计算为两个堆的根的平均值。
我的博客中提供了Scheme和Python中的代码。
