每日算法（四十五）-java找出topK的值

淩亂°似流年 2023-07-24 13:28 34阅读 0赞

每日算法（四十五）-java找出topK的值   
这里用的方法的堆排序的思想(如果堆排序不是很清楚可以看之前的排序算法里的堆排序），构造容量位K的小顶堆，即数组前K个元素构造出的堆，堆积为最小值，之后将堆顶分别于剩下的所有元素依次进行比较，比堆顶大则交换，再进行调整，代码如下

public class TopK \{  
public int findTopK(int arr\[\] ,int k)\{  
    //构建一个K容量的堆，堆顶为最小值  
    buildHeap(arr,k);  
    //从K到之后的元素依次与堆顶比较，比堆顶大则交换，然后再调整里面的堆  
    for(int i=k;i<arr.length;i++)\{  
        if(arr\[i\]>arr\[0\])\{  
            arr\[0\]=arr\[i\];  
            adjustHeap(arr,0,k);  
    \}  
        \}  
    return arr\[0\];  
\}

//构建堆  
private void buildHeap(int\[\] arr, int length) \{  
    //从最后一个非叶子节点开始。  
    for(int i=length/2-1;i>=0;i--)\{  
        adjustHeap(arr,i,length);  
    \}  
\}  
//调整堆  
private void adjustHeap(int\[\] arr, int i, int length) \{  
    int temp=arr\[i\];  //保存父节点的值  
    for(int k=2\*i+1;k<length;k=k\*2+1)\{  
        if(k+1<length&&arr\[k\]>arr\[k+1\])\{           //左孩子>右孩子，则取右孩子  
            k++;  
        \}  
        if(temp<=arr\[k\])\{  
            break;  
        \}else\{            //根节点>左右孩子结点，则交换  
            arr\[i\]=arr\[k\];  
            i=k;  
        \}  
        \}  
        arr\[i\]=temp;  
    \}

public static void main(String\[\] args) \{  
    int arr\[\]=\{19, 8, 27, 6, 315, 14, 99\};  
    TopK to=new TopK();  
    int reslut=to.findTopK(arr, 4);  
    System.out.println(reslut);  
\}  
\}