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

维基百科 http://en.wikipedia.org/wiki/Heap_(data_structure)#Heap_applications says:

选择算法：找到最小值， 最大值，最小值和最大值，median， 或者 甚至第 k 大元素也可以是 使用堆在线性时间内完成。

它只说可以做到，而不是如何做到。

您能给我一些关于如何使用堆来完成此操作的开始吗？

您可以使用最小-最大-中值堆在恒定时间内查找最小值、最大值和中值（并花费线性时间来构建堆）。您可以使用顺序统计树来查找第 k 个最小/最大值。这两种数据结构都在这篇关于最小-最大堆的论文 [PDF] http://cg.scs.carleton.ca/%7Emorin/teaching/5408/refs/minmax.pdf。最小-最大堆是在最小堆和最大堆之间交替的二元堆。

来自论文：

最小-最大-中值堆是具有以下属性的二叉树：

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

2. 根的左子树是大小为上限[((n-1)/2)]的最小-最大堆Hl，包含小于或等于中位数的元素。右子树是大小为 Floor[((n-1)/2)] 的最大最小堆 Hr，仅包含大于或等于中位数的元素。

论文接着解释了如何构建这样的堆。

更彻底地阅读本文后，似乎构建最小-最大-中值堆需要您首先找到中位数（FTA：“使用任何一种已知的线性时间算法查找所有 n 个元素的中值”）。也就是说，一旦构建了堆，您只需保持左侧的最小-最大堆和右侧的最大-最小堆之间的平衡即可维持中位数。 DeleteMedian 将根替换为最大-最小堆的最小值或最小-最大堆的最大值（以保持平衡的为准）。

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