关于：一道腾讯面试题:从大量数字中取出top100
一道腾讯面试题:从大量数字中取出top100
http://www.iteye.com/topic/628707
虽然题目并不难，但看到许多的人回复了，当然有回复的水平高的也有低的反正各种回复千奇百怪。
能想到用二叉树或堆来做的算想对思路了，用多线程部分排序的感觉至少思路上就差得远了。
有个兄弟第一时间用TreeSet给出了代码，当然代码很简单，如下：

private static void top100() {// TreeSet<Integer> tree = new TreeSet<Integer>();PriorityQueue<Integer> heap = new PriorityQueue<Integer>(100);int n = 100000000;int[] arr = new int[n];Random ran = new Random();long start = System.currentTimeMillis();for (int i = 0; i < n; i++) {arr[i] = ran.nextInt(n);}System.out.println(System.currentTimeMillis() - start);start = System.currentTimeMillis();for (int i = 0; i < arr.length; i++) {if (heap.size() < 100) {heap.add(arr[i]);} else if (heap.peek() < arr[i]) {heap.poll();heap.add(arr[i]);}}System.out.println(System.currentTimeMillis() - start);System.out.println(heap);}

改成最小堆后，经测试，最小堆花费1800毫秒左右的时间，TreeSet花费的时间大概3600毫秒，接近2倍的差距。


ps：JVM内存改大点，否则可能申请不到1亿的数组 -Xms128M -Xmx1024M 1 楼 rain_liang 2011-10-15 用类快速排序吧？