median for any x in a stream of numbers

Use two heaps, maxheap and minheap, such that:

maxheap: for numbers < median
minheap: for numbers > median
maxheap has at most 1 element more than minheap

process-stream(stream):
    // maxheap (+1), minheap
    maxheap = new // for numbers < median
    minheap = new // for numbers > median
    foreach x in stream:
        if maxheap.count() > minheap.count():
            if x >= maxheap.top():
                minheap.insert(x)
            else:
                top = maxheap.displace(x)
                minheap.insert(top)
        else: // maxheap.count() == minheap.count()
            if maxheap.isempty() || x <= minheap.top():
                maxheap.insert(x)
            else:
                top = minheap.displace(x)
                maxheap.insert(top)

// interface
heap:
    x top():
    insert(x):
    // return top, replace top with x and heapify
    x displace(x): //avoids delete() and insert(x), O(logn)

get-median():
    if maxheap().isempty():
        throw
    if maxheap.count() > minheap.count():
        return maxheap.top()
    else: // maxheap.size() == minheap.size()
        return (maxheap.top() + minheap.top()) /2

time: O(nlogn)
space: O(n)

[Hat tip to ctci]