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

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. 从给定数组构建最大堆(h(

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

7
/     
6       3
/      / 
5   4   2   1

2. 从堆h的叶子(ceil(n/2)(元素构建最大堆(h1(

5     
/ 
4   2
/
1

3. 从堆h的内部节点(floor(n/2)(元素构建最小堆(h2(

3
/ 
7   6

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

4. 如果n为奇数，则返回max(h1[0],h2[0])

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

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

算法

你只需要一堆。

将值的前一半(向上取整(放在最小堆中。然后，对于其余的值，检查每个值是否小于堆的根。如果是，请忽略该值。如果不是，那么用更大的值替换根的值，并堆积堆，这样新值就会筛选到堆中的一个好位置。

完成此操作后，您知道所有大于中值的值都在树中，并且它还包括表示中值的一个或两个值。如果输入的值为奇数，则根为中值。如果是偶数，则从堆中提取根值，并将其与提取后成为根的值进行平均。