kth minimum element

actually , I am solving a problem:

A list is there in which infinite numbers(approx 1 lakh) are there, and i am reading one by one. At any point of time, I am asked to return the kth(it is given initally) minimum element from the elements read so far.

my approach: I know this question will be solved by using heap(min or max). But , i am not getting how to use heap here? Can any one please give me hints that how heaps will be used here ? whether i should use min or max heap ? please help. thanks.

[rithish]

finding a minimum element means finding a smallest number in an array???

[TrustyTony]

You just need to put next element in order to sorted data structure and drop biggest (k+1st) if size exceeds k. The answer is kth element if length is k, error otherwise (less than k values read)

[deceptikon]

A list is there in which infinite numbers(approx 1 lakh)

1 lakh is hardly infinite. Hell, I wouldn't be against bubble sorting an array of 100,000 items on modern hardware, and bubble sort is the canonical "slow" algorithm.

I know this question will be solved by using heap(min or max).

That seems awkward to me. Unless there are any specific rules to this problem that require a clever approach, I'd probably go with sorted insertion into a collection that has efficient search properties, then just search for the kth element on request. This could be as simple as a dynamic array, though there may be issues with a sorted insertion since it involves lots of data movement.

[sfuo]

At any point of time, I am asked to return the kth(it is given initally) minimum element from the elements read so far.

When I read this I can interperet it three different ways:
1) You are at the 'kth' element and you want to know what the minimum element so far is
2) You are at the 'kth' element and you want to know what the minimum element at any point before the 'kth' point is
3) You are at the 'kth' element and you want to know what the 'nth' minimum element is (eg numbers are 10, 9, 11, 14, 15, 8 -- 3rd minimum element would be 8)

The first option would be very easy since you would just read in and check if the current minimum is less than the read in value, if not then the read in value is the new minimum.

The second option would require you to keep a history of some sort which tells you where the minimum changed and what it became, then you would have to find the point that is less than or equal to the 'kth' element.

The third option would be like the second option but instead of checking where it changed you just access the history array (or other container) at the 'kth' index.

When asking questions you have to be clear as to what is going on.

When asking questions you have to be clear as to what is going on.

let's say I have read 100 th element and somebody has given me k as "3". So at reading 100th element, he suddenly asks me : what is kth(3 here) smallest element yet ? So , then i have to answer in best speedy approach. i hope ypu got what the question is. thanks

[sfuo]

So if you were to go based off my previous post you would pick option #3.

This would be pretty much instant because all the minimum number locations and values have already been saved into an array.

Another approach to this would be to do as deceptikon and pyTony suggested, which is sorting the list and then iterating to the kth element of the sorted list. This would take a bit longer since you have to sort a list that could be very large. However I haven't actually bothered with sorting large containers so I wouldn't know if it would be that big of an issue.