Question: 1. Suppose given an array of size n, with sorted values.
2. In iteration i, a new random-generated value is given, and inserted into the end of the array.
3. The array is then resorted, and discard the least value item.
4. After iteration n, the retained array will contain the largest value items.

For example, in Java syntax, it will be something like:

```
List l = new ArrayList();
l.add(new Integer(2));
l.add(new Integer(3));
l.add(new Integer(6));
l.add(new Integer(9));

Random rand = new Random();
for (int i=0; i < n; i++) {
  l.add(new Integer(rand.nextInt(1000)));
}    
Collections.sort(l);
l.remove(0);

```

But it seems it's inefficient. Any better algorithm?

Answer: 
This will keep the size at 4 and do what you want as I understand it.

```
SortedSet<Integer> set = new TreeSet<Integer>();
set.add(2);
set.add(3);
set.add(6);
set.add(9);
Random rand = new Random();
for (int i=0; i < n; i++) {
  int i = rand.nextInt(1000);
  set.remove(set.first());
  set.add(i);
}    

```
Do you really need an online one item at a time algorithm? Or are you actually parsing a larger collection of data and just want the top n items? If it's the latter, look at [partial qsort](http://www.siam.org/meetings/analco04/abstracts/CMartinez.pdf).