算法二：部分排序
题目要求是求出Top 10，因此我们没有必要对所有的Query都进行排序，我们只需要维护一个10个大小的数组，初始化放入10个Query，按照每个Query的统计次数由大到小排序，然后遍历这300万条记录，每读一条记录就和数组最后一个Query对比，如果小于这个Query，那么继续遍历，否则，将数组中最后一条数据淘汰(还是要放在合适的位置，保持有序)，加入当前的Query。最后当所有的数据都遍历完毕之后，那么这个数组中的10个Query便是我们要找的Top10了。
不难分析出，这样，算法的最坏时间复杂度是N*K， 其中K是指top多少。
算法三：堆
在算法二中，我们已经将时间复杂度由NlogN优化到N*K，不得不说这是一个比较大的改进了，可是有没有更好的办法呢？
分析一下，在算法二中，每次比较完成之后，需要的操作复杂度都是K，因为要把元素插入到一个线性表之中，而且采用的是顺序比较。这里我们注意一下，该数组是有序的，一次我们每次查找的时候可以采用二分的方法查找，这样操作的复杂度就降到了logK，可是，随之而来的问题就是数据移动，因为移动数据次数增多了。不过，这个算法还是比算法二有了改进。
基于以上的分析，我们想想，有没有一种既能快速查找，又能快速移动元素的数据结构呢？
回答是肯定的，那就是堆。
借助堆结构，我们可以在log量级的时间内查找和调整/移动。因此到这里，我们的算法可以改进为这样，维护一个K(该题目中是10)大小的小根堆，然后遍历300万的Query，分别和根元素进行对比。
思想与上述算法二一致，只是在算法三，我们采用了最小堆这种数据结构代替数组，把查找目标元素的时间复杂度有O（K）降到了O（logK）。
那么这样，采用堆数据结构，算法三，最终的时间复杂度就降到了N*logK，和算法二相比，又有了比较大的改进。
至此，算法就完全结束了，经过上述第一步、先用Hash表统计每个Query出现的次数，O（N）；然后第二步、采用堆数据结构找出Top 10，N*O（logK）。所以，我们最终的时间复杂度是：O（N） + N'*O（logK）。（N为1000万，N'为300万）。
js如何使用堆实现Top K 算法?
1. 使用堆算法实现Top，时间复杂度为 O(LogN)
function top(arr,comp){ if(arr.length == 0){return ;} var i = arr.length / 2 | 0 ; for(;i >= 0; i--){ if(comp(arr[i], arr[i * 2])){exch(arr, i, i*2);} if(comp(arr[i], arr[i * 2 + 1])) {exch(arr, i, i*2 + 1);} } return arr[0]; } function exch(arr,i,j){ var t = arr[i]; arr[i] = arr[j]; arr[j] = t; }
2. 调用K次堆实现，时间复杂度为 O(K * LogN)
function topK(arr,n,comp){ if(!arr || arr.length == 0 || n <=0 || n > arr.length){ return -1; } var ret = new Array(); for(var i = 0;i < n; i++){ var max = top(arr,comp); ret.push(max); arr.splice(0,1); } return ret; }
3.测试
var ret = topK(new Array(16,22,91,0,51,44,23),3,function (a,b){return a < b;}); console.log(ret);
以上就是为大家分享的使用堆实现Top K算法，何为Top K算法，希望对大家的学习有所帮助。
您可能感兴趣的文章: