java - 有一个算法问题想请教，给定一亿个数，如何用最快的方法取出其中最大的三个数。

Question

最近有一个java大神，是蚂蚁支付宝的哦，问了我这么一个问题。我的回答是先将数组分解成两百个小数组或者更多，在开两百个thread进行排序，取最大，然后对这两百个数进行排序，取前三。其实我的思路根本就没有涉及到算法层面，也只是暴力破解。其实这不是最好的做法，因为这样会严重的浪费资源，然后他的回答是堆排序。我的问题是堆排序是怎样实现的，最好用代码体现出来。

Answer 1

Why do we need to sort the top three? Just open up three new variable spaces to save the intermediate results.

This method still has advantages when the complexity is O(nk)，n是数据总量，k是要获取的数据数量。排序无论是堆排还是快排都是O(nlogn)。当k小于log(2, 10 ** 8). If it is too large, it will degenerate into insertion sort.

Answer 2

There are N (N>>10000) integers, find the top K largest numbers among them. (Called Top k algorithm problem). Due to (1) a large amount of input data; (2) only the first K, it is quite undesirable to save and sort the entire input data. This problem can be handled using a min-heap of data structures.

In the minimum heap, the value of each non-leaf node must not be greater than the value of the child node. In this way, a minimum heap containing K nodes can be used to save the K current maximum values ​​(of course the root node is the minimum value among them). Every time there is data input, it can be compared with the root node first. If it is not greater than the root node, discard it; otherwise, replace the root node value with the new value. And adjust the minimum heap.

Since only K pieces of data are saved, the time complexity of the minimum heap is adjusted to O(logK), so the time complexity of the TOp K algorithm (problem) is O(nlogK).

Answer 3

Just search
http://www.cnblogs.com/skywang12345/p/3610187.html

See the introduction to algorithms for proof and derivation

But you don’t need to pile it up, after all, you are only looking for 3 numbers...

Answer 4

Isn’t this a typical Top K question? You can search Top K on Baidu

Answer 5

topn is not wrong if he says that the safe answer is stacking. The question is taken from these 3. . . Such a small number

Answer 6

It’s heap sort a

Answer 7

topk solution

Answer 8

If you want to be fastest, I think bitmap sorting is the fastest I have ever seen.