Finding the median of an unsorted array

algorithm heap median
Luv picture Luv · May 19, 2012 · Viewed 116.4k times · Source

To find the median of an unsorted array, we can make a min-heap in O(nlogn) time for n elements, and then we can extract one by one n/2 elements to get the median. But this approach would take O(nlogn) time.

Can we do the same by some method in O(n) time? If we can, then please tell or suggest some method.

Answer

Sergey Kalinichenko picture Sergey Kalinichenko · May 19, 2012

You can use the Median of Medians algorithm to find median of an unsorted array in linear time.

Related questions

Find running median from a stream of integers

Possible Duplicate: Rolling median algorithm in C Given that integers are read from a data stream. Find median of elements read so far in efficient way. Solution I have read: We can use a max heap on left side to …

Read More
How do I find the median of numbers in linear time using heaps?

Wikipedia says: Selection algorithms: Finding the min, max, both the min and max, median, or even the k-th largest element can be done in linear time using heaps. All it says is that it can be done, and not how. …

Read More
How can building a heap be O(n) time complexity?

Can someone help explain how can building a heap be O(n) complexity? Inserting an item into a heap is O(log n), and the insert is repeated n/2 times (the remainder are leaves, and can't violate the heap property). …

Read More