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

Question

我需要找到给定数组的中位数，并限制仅使用堆。

我知道用于查找中位数的线性选择算法。 以下方法(仅基于堆)正确吗？

1. 根据给定数组构建最大堆 (h)
2. 从堆 h 的叶子 (ceil(n/2)) 构建最大堆 (h1)
3. 从堆 h 的内部节点 (floor(n/2)) 构建最小堆 (h2)
>
4. 如果n为奇数，则返回max(h1[0],h2[0])
   否则返回(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。

算法

您只需要一个堆。

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

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