An answer to this question on Stack Overflow.

Question

A way of finding the median of a given set of n numbers is to distribute them among 2 heaps. 1 is a max-heap containing the lower n/2 (ceil(n/2)) numbers and a min-heap containing the rest. If maintained in this way the median is the max of the first heap (along with the min of the second heap if n is even). Here's my c++ code that does this:

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

We know that the heapify operation has linear complexity . Does this mean that if we insert numbers one by one into the two heaps as in the above code, we are finding the median in linear time?

Answer

This is a great question, especially since you can find the median of a list of numbers in O(N) time using Quickselect.

But the dual priority-queue approach gives you O(N log N) unfortunately.

Riffing in binary heap wiki article here, heapify is a bottom-up operation. You have all the data in hand and this allows you to be cunning and reduce the number of swaps/comparisons to O(N). You can build an optimal structure from the get-go.

Adding elements from the top, one at a time, as you are doing here, requires reorganizing every time. That's expensive so the whole operation ends up being O(N log N).