首页 > 代码库 > 使用堆实现Top K 算法 JS 实现
使用堆实现Top K 算法 JS 实现
1. 使用堆算法实现Top，时间复杂度为 O(LogN)
2. 调用K次堆实现，时间复杂度为 O(K * LogN)
3.测试
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 算法 JS 实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。