使用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);
        }
    }
}

我们知道 heapify操作具有线性复杂性.这是否意味着如果我们将数字一个接一个地插入到上面的代码中的两个堆中,我们发现线性时间的中位数？

Answer 1

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

考虑一个最小堆,您可以按递增顺序插入值流.堆顶部的值是最小的,因此每个值一直向下到达堆的底部.只考虑插入的值的后半部分.此时堆将具有非常接近其完整高度,即log(n),因此每个值都会向下插入log(n)个插槽,插入n/2值的成本为O(n log(n))

如果我按照递增顺序向您的中值查找算法提供值流,则必须做的事情之一就是按递增顺序从值流构建最小堆,因此中值查找的成本为O(n log(n) )).事实上,最大堆将进行大量删除和插入,但这只是一个常数因素,所以我认为整体复杂性仍然是O(n log(n))