相关疑难解决方法(0)

找到给定的一组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操作具有线性复杂性.这是否意味着如果我们将数字一个接一个地插入到上面的代码中的两个堆中,我们发现线性时间的中位数？