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 min-heap to store the data, and after each insertion of a new random value, delete the min in O(1) time.

After n iterations, perform n extract-min's to get the sorted list.
Here is another solution which merges the operations into just a search, an array copy and a value set. This avoid the need for sorting or loops.

```
public static <T extends Comparable<T>> 
        void insertAndRemoveSmallest(T[] array, T t) {
    int pos = Arrays.binarySearch(array, t);
    if (pos < 0) pos = ~pos;
    // this is the smallest entry so no need to add it and remove it.
    if (pos == 0) return;
    pos--;
    // move all the entries down one.
    if (pos > 0) System.arraycopy(array, 1, array, 0, pos);
    array[pos] = t;
}

```

This program

```
public static void main(String... args) {
    Integer[] ints = {2, 3, 7, 6, 9};
    System.out.println("Starting with " + Arrays.toString(ints));
    for (int i : new int[]{5, 1, 10, 8, 8}) {
        insertAndRemoveSmallest(ints, i);
        System.out.println("After adding " + i + ": " + Arrays.toString(ints));
    }
}

```

prints

```
Starting with [2, 3, 7, 6, 9]
After adding 5: [3, 5, 7, 6, 9]
After adding 1: [3, 5, 7, 6, 9]
After adding 10: [5, 7, 6, 9, 10]
After adding 8: [7, 6, 8, 9, 10]
After adding 8: [6, 8, 8, 9, 10]

```