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.
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).
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
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.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).
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...
Isn’t this a typical Top K question? You can search Top K on Baidu
topn is not wrong if he says that the safe answer is stacking. The question is taken from these 3. . . Such a small number
It’s heap sort a
topk solution
If you want to be fastest, I think bitmap sorting is the fastest I have ever seen.