1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

import java.util.Scanner;
 
/** Program to read names and times into a max-heap and print the
 * K names with the smallest times.
 */
public class TopK {
  public static void main(String[] args) {
    int k = -1;
    try { k = Integer.parseInt(args[0]); }
    catch(ArrayIndexOutOfBoundsException | NumberFormatException ex) {
      System.err.println("You need to specify K as a command-line argument.");
      System.exit(1);
    }
 
    Scanner in = new Scanner(System.in);
    // This heap will hold the smallest k entries at any given time
    TimeHeap bestTimes = new TimeHeap();
 
    while (in.hasNext()) {
      String name = in.next();
      long time = in.nextLong();
      // insert into the max-heap
      bestTimes.insert(time, name);
      // if more than k entries, remove the worst one
      if (bestTimes.size() > k) bestTimes.removeMax();
    }
 
    // count down the smallest times
    for (int place = bestTimes.size(); place >= 1; --place) {
      System.out.print(place);
      System.out.print(". ");
      System.out.println(bestTimes.removeMax());
    }
  }
}