design a Queue that supports getMedian function

Question

This is an interview question. You need to design a queue which holds integer values and has a getMedian() function that returns median element of current queue. You can use O(n) extra space.

Can getMedian() be implemented with time complexity < O(n)?

For Example: When the queue has the following values (2, 1, 2, 2, 6, 4, 2, 5) this method returns 2 and doesn't remove that object.

Answer 1

The known implementation for your problem is as so:

What you need to implement is 2 heaps, one will be a min-heap and the other a max-heap.
Also you will need an integer to tell us the number of objects in your queue.

The constraints for the heaps are as follows:
1. The min-heap will have the larger objects of your queue
2. The max-heap will have the smaller objects of your queue
3. The max-heap will have the same or 1 more object than your min-heap

That way, if you have an odd number of objects the median would be exactly the max object in your max-heap. If you have an even number of objects your median would then be the average of both roots of your heaps (max of max-heap, min of min-heap).

It is important to notice that if your heaps become uneven, for instance if you will "pop" from a certain heap, you will need to remove from the other heap and move it. But thats not a problem as all you need to deal with is the roots of your heaps and nothing more.

The time complexity of getMedian becomes O(1)

Just found an article on the subject: link

Answer to comment

The max-heap holds the half smallest elements.
When you add a new number to the queue, you first check what is the number of objects in the queue.
if the number you are adding is an even number, it means it needs to be added to the max-heap as both queues are equal in size.
You then see what the max in the max-heap is.
If it is larger than ur number, you can just insert it into the max-heap.
if it is smaller, meaning ur new number might be bigger than a number in the min-heap.
so you see what the min in the min-heap is.
if your number is smaller than the min, than you can insert it in the max-heap, if it is bigger, then u move the min in the min-heap to the max-heap, and insert your new number in the min-heap.
If the number is an odd number, you need to add to the min-heap as the max-heap has one more, and so on..

Its a bit complicated but if you still dont understand I dont mind psuedo coding it for you