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);  

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。