How do I get the largest K massive data

This may be an algorithm problem with great depth in metaphysics , Because the people in this meeting can design excellent algorithms , People who can't do it may have nowhere to start . Huge amounts of data top K problem , It is reflected everywhere in the products of Internet manufacturers , For example, wechat's step counting software , According to the statistics K name , And then sort it .

Of course, there are 100 million floating-point numbers for similar problems , How to find out the biggest 10000 individual . In fact, the code skills involved are memory processing and data De duplication optimization , Deal with the massive data that needs to occupy a large amount of memory space through various methods . There are several ways , Including the stupidest and wisest plan , You can blow water during the interview .

Memory allows , Sort all directly

This is probably the most direct, simple and crude way , But you know , Our premise is massive data , This method is a scheme , But it's definitely unreliable . Sort all from large to small, then , We take the head directly K individual , Methods consume a lot of memory and are not efficient , Did a lot of idle work , Not recommended . Of course, if in an oral interview , When your brain is short circuited, you can put forward this first .

Memory allows , Divide and conquer method

In fact, the idea of partition includes fast sorting and merging sorting . The first division of ideas is to continuously divide the data into N Share , Governance is to find the biggest... In each data K Number .

Minimum heap method （ Also called partial elimination method ）

A partial elimination method . Before reading K Number , Build a minimum heap . Then compare all the remaining numbers with the top of the smallest heap in turn , If less than or equal to the heap top data , Then continue to compare the next ; otherwise , Remove the heap top element , And insert the new data into the heap , Readjust the minimum heap size . After traversing all the data , The data in the smallest heap is the largest K Number .

The time complexity is O（n+m^2）（ among m by K, such as 10000）