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

Question

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

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

1. 从给定数组构建一个max-heap（h）
2. 从堆h
的叶子（ ceil（n/2））构建一个max-heap（ h1）
3. 从堆h
的内部节点（ 楼层（n/2））构建一个min-heap（ h2）
4. 如果n是奇数返回max（h1[0]， h2[0]）
   否则返回（h1[0]h2[0]）/2

Answer 1

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

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

1. 从给定数组构建max-heap（h）

输入碰巧已经被构造为最大堆。它是：

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

                 5     
                / \
               4   2
              /
             1

                 3
                / \
               7   6

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

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

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

您只需要一个堆。

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

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