JS 实现 使用堆实现Top K 算法

2019PHP高薪工程师学习路线图....>>>

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