仅使用堆从任意整数数组中查找中位数

Question

我需要找到给定数组的中位数，但有限制只能使用 堆。

我知道用于查找中位数的线性选择算法。 以下方法（仅基于堆）是否正确？

1. 从给定的数组
构建一个最大堆（h）
2. 从堆 h
的叶子 (ceil(n/2)) 构建最大堆 (h1)
3. 从堆 h
的内部节点 (floor(n/2)) 构建一个最小堆 (h2)
4. 如果n是奇数returnmax(h1[0],h2[0])
   否则 return (h1[0] + h2[0])/2

Answer 1

不，你提出的算法一般不会起作用。它错误地假设最大堆的叶子节点的值不能大于中值。这不是真的。这是一个反例：

输入：[7、6、3、5、4、2、1]

1. build max-heap (h) from given array

输入恰好已经被构造为最大堆。它是：

                     7
                   /   \  
                 6       3
                / \     / \
               5   4   2   1
              

2. build max-heap (h1) from the leaves (ceil(n/2)) elements of heap h

                 5     
                / \
               4   2
              /
             1

3. build min-heap (h2) from the internal nodes (floor(n/2)) elements of heap h

                 3
                / \
               7   6

请注意，在这一步和上一步中创建这些较小的堆对于您的目的而言并不是真正必要的，因为您真正感兴趣的只是从叶子中获取最大值，从内部获取最小值节点。为此，一个简单的扫描就足够了，而不需要实际再创建两个堆。

4. if n is odd return max(h1[0],h2[0])

 max(h1[0],h2[0]) = 5

然而正确答案不是 5，而是 4。

算法

你只需要一堆。

将值的前半部分（向上舍入）放入最小堆中。然后对于剩余的值，检查每个值是否小于堆的根。如果是这样，请忽略该值。如果不是，则将根的值替换为较大的值，并对堆进行堆化，以便新值筛选到堆中的合适位置。

这样做之后，你知道所有大于中位数的值都在树中，并且还包括代表中位数的一两个值。如果输入有奇数个值，根就是中位数。如果是偶数，则从堆中拉取根值，并与本次提取后成为根的值进行平均。