Thread: Find nth largest number in a stream of numbers

Write a program to find nth largest number from a stream of numbers.

The best solution to this is to create a max-heap(of n) integers on a running stream of numbers. When a number is read from the stream, we refresh the max-heap to fix the new number from the stream inside the heap. This is a log(n) operation.
Finding the nth largest number would also be log(n) [if I am not mistaken]

finding nth largest in a heap will be n*logn
correct me if i'm wrong

it will be logn only

I think using min-heap of size n would be better.

1)Read number from stream and compare it with root in min-heap.
2)If number read is lesser, throw it.
3)If number is greater than root, overwrite root with the number and heapify. (O(logn))
4)After all the numbers are read, the number at the root is nth largest.

So worst case complexity is O(k*logn) where k is numbers read from stream.

Quickselect
QuickSelect
MIT's Introduction to Algorithms, Lecture 6: Order Statistics - good coders code, great reuse