题解 | #最小的K个数# 手动实现优先级队列 Java

import java.util.ArrayList;

public class Solution {
   public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        int len = input.length;
        //从这k个数中，有字节点的节点开始
        for(int i=(k-1)/2;i>=0;i--){
          //对k个数进行 最大堆构建
            shiftDown(input,i,k-1);
        }
		//构建好的最大堆，第一个数是最大的
     	//未参与构建最大堆的数和最大堆堆顶比较
        for(int i=len-1;i>=k;i--){
          //如果最大堆堆顶小于外面的数
            if(input[i]>=input[0]){
                continue;
            }else{
              	//最大堆堆顶大于外面的数，则将外面的数换入最大堆
                swap(input,i,0);
              //重新构建最大堆
                shiftDown(input,0,k-1);
            }
            
        }
        ArrayList<Integer> res = new ArrayList();
        for(int i=0;i<k;i++){
            res.add(input[i]);
        }
        return res;
    }
    void shiftDown(int[] input,int index,int len){
      //最大堆是一颗完全二叉树
      //indexLeftSon = index * 2 + 1;
        while(2*index+1<=len){
            int j = index*2+1;
          	//找出左右孩子中的最大值
            if(j+1<=len && input[j]<input[j+1]){
                j++;
            }
          //如果index父节点已经是最大的
            if(input[index]>=input[j]){
                break;
            }
          	//交换孩子中的最大值和index节点
            swap(input,index,j);
            index = j;
        }
    }
    void swap(int[] input , int i , int j){
        int temp = input[i];
        input[i] = input[j];
        input[j] = temp;
    }
}