题解 | #最小的K个数#

import java.util.ArrayList;

public class Solution {
    /**
    堆排序
    */
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> ret = new ArrayList<>() ;
        if(input == null || input.length == 0 || k == 0 || k > input.length) {
            return ret ;
        }
        //创建小顶堆
        for(int i = (input.length-2)/2 ; i >= 0 ; i --) {
            heapify(input,input.length,i) ;
        }
        //开始交换
        for(int j = input.length-1,q = 1 ; j >= 0 && q <= k ;q++, j --) {
            swap(input , 0 , j) ;
            ret.add(input[j]) ;
            heapify(input , j , 0) ;
        }
        return ret ;
    }
    /**
    调整堆：len表示调整的堆对应的数组的长度 ， i表示调整哪一个结点（默认该节点的子节点们已经是堆了）
    */
    public void heapify(int[] arr , int len ,int i) {
        if(i >= len) {
            return  ;
        }
        int l = i * 2 + 1 ;
        int r = i * 2 + 2 ;
        int minIndex = i ;
        if(l < len && arr[minIndex] > arr[l]) {
            minIndex = l ;
        }
        if(r < len && arr[minIndex] > arr[r]) {
            minIndex = r ;
        }
        if(minIndex != i) {
            swap(arr , i , minIndex) ;
            heapify(arr,len , minIndex) ;
        }
    }
    public void swap(int []arr , int i , int j) {
        int temp = arr[i] ;
        arr[i] = arr[j] ;
        arr[j] = temp ;
    }
}