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

Question

找到给定n个数字集的中位数的一种方法是将它们分布在2堆中。1是一个包含较低n/2（ceil（n/2））数字的max-heap和一个包含其余数字的min-heap。如果以这种方式保持，中位数是第一堆的最大值（如果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);
        }
    }
}

我们知道堆化操作具有线性复杂性。这是否意味着如果我们像上面的代码一样将数字一个接一个地插入两个堆中，我们就会找到线性时间的中位数？

Answer 1

这是一个很好的问题，特别是因为您可以使用Quickselect在O（N）时间内找到数字列表的中位数。

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

在这里重复二进制堆wiki文章，heapify是一个自下而上的操作。您手头有所有数据，这允许您狡猾并将交换/比较的数量减少到O（N）。您可以从一开始就构建最佳结构。

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

Answer 2

>

当有一个元素时，由于单个元素位于单个堆中，因此该步骤的复杂性为log1。

当有两个元素时，这个步骤的复杂度是Log 1，因为我们在每个堆中有一个元素。

当有四个元素时，这个步骤的复杂度是Log 2，因为每个堆中有两个元素。

因此，当有n个元素时，复杂度是Log n，因为每个堆中有n/2个元素

• 添加一个元素;以及，
• 从一个堆中删除元素并将其添加到另一个堆;

这需要O（对数n/2）=O（对数n）时间。

因此，跟踪n个元素的中位数基本上是通过执行：

2*（Log 1 Log 2 Log 3... Log n/2）步骤。

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

可以用两种方式处理上述求和。一种方法给出了一个更严格的界限，但通常不太常见。下面是：

• Log a Log b＝Log a*b（根据对数的性质）
• 所以，求和实际上是Log（（n/2）！）=O（对数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

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

考虑一个以递增顺序插入值流的最小堆。堆顶部的值是最小的，因此每个值都会一直滴到堆的底部。只考虑插入的值的最后一半。此时堆将非常接近其完整高度，即log（n），因此每个值都会滴到log（n）槽中，插入n/2值的成本为O（n log（n））

如果我向您的中值查找算法呈现一个以升序排列的值流，它必须做的事情之一是从一个以升序排列的值流中构建一个最小堆，这样中值查找的开销为O(n log(n))。事实上，max heap将会执行大量的删除和插入操作，但是这只是一个常量因素，所以我认为总的复杂度仍然是O(n log(n))