使用堆查找未排序数组的中位数

Question

有没有办法使用堆找到未排序数组的中位数？如果可能的话，是不是比先排序再求中位数更有效？

Answer 1

这里的技巧是使用两个堆，一个是最小堆，另一个是最大堆。我不会详细介绍，但是以下几点足以实现所需的算法。

1. 最小堆的顶部是大于或等于均值的最小元素
2. 最大堆的顶部是小于或等于平均值​​的最大元素。

现在回到你的第二个问题，只有当你想找到 运行 中位数时才有效，即每次向数组中插入一个新元素后的中位数。

如果只想计算一次所有数组元素的中位数，那么排序是个好主意。

希望对您有所帮助。