如何使用堆在线性时间中找到数字的中位数？

您将使用min-max-
median堆在恒定时间内查找min，max和中位数（并花费线性时间来构建堆）。您可以使用订单统计树来找到第k个最小/最大值。本文在最小最大堆中描述了这两种数据结构[pdf链接]。最小最大堆是在最小堆和最大堆之间交替的二进制堆。

从本文中可以得出：最小-最大中值堆是具有以下属性的二进制堆：

1）所有元素的中位数位于根

2）根的左子树是大小为[[（（n-1）/ 2）]的最小-最大堆H1，其中包含小于或等于中位数的元素。右边的子树是大小为floor [（（（n-1）/
2）]的最大-最小堆Hr，其中仅包含大于或等于中位数的元素。

本文继续说明如何构建这样的堆。

编辑：更深入地阅读本文后，似乎要构建最小-最大-中位数堆首先需要找到中位数（FTA：“使用任何已知的线性时间算法查找所有n个元素的中位数”）
。就是说，一旦建立了堆，您就可以简单地通过保持左侧的min-max堆和右侧的max-min堆之间的平衡来维护中间值。DeleteMedian用最大-
最小堆的最小值或最小-最大堆的最大值（以保持平衡的状态为准）替换根。

因此，如果您计划使用最小-最大-中值堆来查找固定数据集的中位数，那么您就是SOL，但是如果您在变化的数据集上使用它，则可以。