I love the editorials for the opportunity to get new ideas on how to tackle a problem. I will study the two heap solution later.

My solution was to use a C++ std::map, which internally is a binary tree and does not invalidate iterators after an insert. (Some other commenters here mentioned something called sortedcontainers, which I think is the same idea.) The resulting complexity should be O(nlogn): logn for an insert in the binary tree, and this is done n times (once for each element in the input array). The idea is simple: keep a "(lower) median" iterator into the tree, and increment/decrement this iterator depending on whether a new value is added above or below the lower median. For an odd number of elements, lower median and median are the same, for even the median is the average of the lower median and the next element.

The tricky part is that, since numbers are allowed to repeat in the input array, one needs a bit of extra logic to keep track of "position" in bins associated to each input number. Code below. A bit ugly, but ya know, the best solution is the one you know and stuff.

c++
vector<double> runningMedian(vector<int> const&a) {
    if(0==a.size())
        return vector<double>();
    map<int,int> aux; 
    aux.insert({a[0],1});
    auto lowerMed = aux.begin();
    vector<double> retq;
    retq.push_back(1.0*(lowerMed->first));
    int pos=0;
    for(int i=1; i<a.size();i++)
    {
        if(!aux.count(a[i]))
            aux.insert({a[i],1});
        else{aux[a[i]]++;}
        if((a[i]<lowerMed->first)&&(i&1))
            pos--;
        else if((a[i]>=lowerMed->first)&&(0==(i&1)))
            pos++;
        if(0>pos)
        {
            lowerMed--;
            pos=lowerMed->second-1;
        }
        else if(lowerMed->second<=pos)
        {
            lowerMed++;
            pos=0;
        }
        if(0==(i&1))
        {
            retq.push_back(1.0*(lowerMed->first));
        }
        else
        {
            auto x=lowerMed;
            if(pos+1>=lowerMed->second)
                x++; 
            retq.push_back(0.5*(lowerMed->first + x->first));
        }
    }
    return retq;
}