TopK问题

典型问题 ：给定一个100亿（N）个数字，让你找出其中前1000（M）大的数字

两种不同解决方案： 1.用一个数组保存刚才的那些数字，直接在这个数组上建大堆，循环1000次进行取堆顶元素+调整操作，就能得到前1000大的元素：O(N)+O(M+logN) 2.先取集合中的1000个元素放到一个数组中，建立一个小堆，建立一个大小为1000的小堆，堆顶元素就是前1000大元素的守门员，再一个一个遍历集合中的数字，依次和守门员进行比较，如果这个元素比守门员大，就把守门员删掉，再把当前的元素入堆，当遍历完所有元素的时候，队中的元素就是前1000大的元素。O(M)+O(N+logM)

在topk问题中，一般N>>M (近似把M看成1) （方法一占用大量的内存空间，推荐方法二）