面试手撕代码常见TopK问题（Java小顶堆实现）

public class TopK{
          
   
        public static void main(String[] args){
          
   
		 int[] data={
          
   3,5,8,7,9,2,4,3,1,6};
		//举例，如获取top5
		int[] top5=topK(data,5);
		//1.先从原始数据中取出topK的前k个数据建立小顶堆
		for(int i=0;i<5;i++){
          
   
		  System.out.println(top5[i]);
		  }
		}//main结束
		//2.建堆，剩下的N-K个数据来一个排序一个
		//3.从data数组中获取最大的k个数
	    public static int[] topK(int[] data,int k){
          
   
		  int[] topk=new int[k];
		  for(inti=0;i<k;i++0){
          
   
		   top[i]=data[i];
		   }
		  //转换成小顶堆
		  MinHeap heap=new MinHeap(topk);
		  //从k开始，即剩下的数，进行遍历并加入到小顶堆
		  for（int i=k;i<data;i++){
          
   
		    int root=heap.getRoot();
		//当当前数据大于堆中根节点，即最小的数，说明在范围之内，先保留
			if（data[i]>root){
          
   
			  heap.setRoot(data[i]);
			  }
		}//for循环结束
		return topk;
	}//topk方法结束
} //TopK类结束

//构建小顶堆的类
public  class MinHeap{
          
   
   //堆的存储结构，数组保存
   private int[] data;
   
   //将数组数据建立小顶堆
   public MinHeap(int[] data){
          
   
      this.data=data;
	  buildHeap();
	  }
	  
	 //具体建立最小堆
   private void bulidHeap(){
          
   
	 for(int i=(data.length)/2-1;i>=0;i--){
          
   
	   heapfy(i);
	   }
	 }
	 
	 //调整堆
	 private void heapify(int i){
          
   
	     int l=left(i);
	     int r=right(i);
	     int smallest=i; 
	 //存在左节点且左节点小于根节点的值
	   if(l<data.length&&data[l]<data[i])
	       smallest=l;
		//存在右节点且右节点小于以上节点的较小值
	 if(r<data.length&&data[r]<data[smallest])
	    smallest=l;
	   if(i==smallest)
	   return;
	   
	   //交换根节点和左右节点中最小的那个值，把根节点的值替换
	   swap(i,smallest);
	   //由于替换影响，需要对子树进行再次排序，直到；
	   heapify(smallest); 
	 }
	 
	  //获取右节点的数组下标
	 private  int right(int i){
          
   
	    return (i+1)<<1;
		}
		//获取左节点的数组下标
	 private int left(int i){
          
   
        return ((i+1)<<1)-1;
        }		
	 //交换元素位置
	 private void swap(int i,int j){
          
   
	   int temp=data[i];
	   data[i]=data[j];
	   data[j]=temp;
	   }  
	 //获取堆中的最小元素，根元素
	 public int getRoot(){
          
   
	    return data[0];
		}
	//替换根元素，并重新heapify
	  public void setRoot(int root){
          
   
	  data[0]=root;
	    heapify(0);
		}
	}
}