使用 2 个堆找到中位数的复杂性

Question

找到一组给定的 n 个数字的中位数的方法是将它们分布在 2 个堆中。 1 是包含较低 n/2 (ceil(n/2)) 个数的最大堆和包含其余数的最小堆。如果以这种方式维护，则中位数是第一个堆的最大值（如果 n 是偶数，则还有第二个堆的最小值）。这是我执行此操作的 C++ 代码：

priority_queue<int, vector<int> > left;
priority_queue<int,vector<int>, greater<int> > right;
cin>>n; //n= number of items
for (int i=0;i<n;i++) {
    cin>>a;
    if (left.empty())
        left.push(a);
    else if (left.size()<=right.size()) {
            if (a<=right.top())
                left.push(a);
            else {
                left.push(right.top());
                right.pop();
                right.push(a);
            }
    }
    else {
        if (a>=left.top())
            right.push(a);
        else {
            right.push(left.top());
            left.pop();
            left.push(a);
        }
    }
}

We know that the heapify operation has linear complexity。这是否意味着如果我们像上面的代码一样将数字一个一个地插入到两个堆中，我们正在寻找线性时间的中位数？

Answer 1

线性时间 heapify 用于从未排序的数组构建堆作为批处理操作的成本，而不是通过一次插入一个值来构建堆。

考虑一个最小堆，您要在其中按递增顺序插入值流。堆顶的值是最小的，所以每个值都会一直滴到堆底。只考虑插入值的后半部分。此时堆的高度将非常接近它的全部高度，即 log(n)，因此每个值都滴入 log(n) 个槽，插入 n/2 个值的成本为 O(n log(n) )

如果我向您的中值查找算法提供一个按升序排列的值流，它必须做的一件事就是从一个按升序排列的值流构建一个最小堆，因此中值查找的成本是 O （n 日志（n））。事实上，最大堆将进行大量删除和插入操作，但这只是顶部的一个常数因素，所以我认为整体复杂度仍然是 O(n log(n))

Answer 2

当有一个元素时，由于单个元素在单个堆中，因此步骤的复杂度为 Log 1。
当有两个元素时，步骤的复杂度为 Log 1，因为我们在每个堆中有一个元素。
当有四个元素时，步骤的复杂度为 Log 2，因为我们在每个堆中有两个元素。

因此，当有 n 个元素时，复杂度为 Log n，因为我们在每个堆中有 n/2 个元素并且

添加一个元素；还有，
从一个堆中删除元素并将其添加到另一个堆中；

花费 O(Log n/2) = O(Log n) 时间。

因此，要跟踪 n 个元素的中位数，基本上可以通过执行以下操作来完成：

2 * ( Log 1 + Log 2 + Log 3 + ... + Log n/2 ) steps.

2 的因数来自于在 2 个堆中执行相同的步骤。

上面的求和可以用两种方式处理。一种方法给出了更严格的界限，但一般情况下遇到的频率较低。开始了：

Log a + Log b = Log a*b（属性的对数）
所以，总和实际上是 Log ((n/2)!) = O(Log n!)。

第二种方式是：

每个值 Log 1、Log 2 ... Log n/2 都小于或等于 Log n/2
由于共有n/2项，总和小于(n/2) * Log (n/2)
这意味着函数的上限为 (n/2) * Log (n/2)
或者，复杂度为 O(n * Log n)。

第二个界限更宽松但更广为人知。

Answer 3

这是一个很好的问题，特别是因为您可以使用 Quickselect.[=12= 在 O(N) 时间内找到数字列表的中位数]

但不幸的是，双优先级队列方法给了你 O(N log N)。

Riffing in binary heap wiki article 这里heapify是自下而上的操作。您掌握了所有数据，这使您可以巧妙地将 swaps/comparisons 的数量减少到 O(N)。您可以从一开始就构建最佳结构。

从顶部添加元素，一次一个，就像您在这里所做的那样，每次都需要重新组织。这很昂贵，所以整个操作最终是 O(N log N).

使用 2 个堆找到中位数的复杂性

Complexity of finding the median using 2 heaps

algorithm

heap

median