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: 
Use a [TreeSet](http://java.sun.com/javase/6/docs/api/index.html?java/util/TreeSet.html) instead of a `List`, it'll maintain the order such that such that the largest value will always be at [SortedSet#last()](http://java.sun.com/javase/6/docs/api/java/util/SortedSet.html#last()). If using 1.6+ you can use [NavigableSet](http://java.sun.com/javase/6/docs/api/index.html?java/util/NavigableSet.html) methods; [pollLast()](http://java.sun.com/javase/6/docs/api/java/util/NavigableSet.html#pollLast()) will return and remove the highest value.

```
NavigableSet<Integer> set = new TreeSet<Integer>();

//... setup data

Integer highest = set.pollLast();

set.add(rand.nextInt(1000));

Integer newHighest = set.pollLast();

```
I'm not sure if the above example would work, what is n? and if you cycle through adding random #'s from 1 to 1,000 you'll always end up with 1000, 999, 998 and 997 - no? I don't think adding a # and then resorting each time is efficient- it would probably be quicker to check each of the four positions and replacing with a higher #.

A lot depends on how many random #'s you'll add, to few # adds and check each of the 4 positions a lot of # adds just assume you get the highest in the range.