Sorry, didn't read till the end of the article before posting the above. Anyway, there is no need for Tarjan's algorithm, since a tighter analysis of a simple heapify-up/heapify-down algorithm shows that it works in O(n).
As for finding the median, this can be always done in O(n) using the so called Selection algorithm. (a particular variant - randomized selection - works very fast in practice)
The only interesting problem is about having a structure such that several(many) extractions of the medians are O(log n) each, with as little overhead is possible for maintaining such a structure (under e.g. insertions of new elements).