题解 | #最小的K个数#

其实我知道就是堆排序，但写出来花了我三个晚上 ac的那一刻真的是太快乐了

堆排序的原理并不复杂 我觉得可以拆分成三部分来看： 1.main函数，这题要求输出堆顶的k个元素，所以需要for循环，每次都要重新调整堆（建堆），输出堆定的元素，然后交换到堆底 这时，我用一个cur_length变量来记录堆的大小 那么既然输出了一个，堆的大小需要-1. 2.建堆，每趟堆排序完成后，都要自下而上地重新调整堆。方法是从最后一棵子树开始调整 3.自上而下调整。由于建堆的过程中，上层元素的调整可能会破坏下层堆，所以，每次调整后，需要从被调整的节点，向下恢复堆。这里用一个递归。

不过我的运行时间好长。。。哪里出现了问题

import java.util.*;
public class Solution {
    
    public void swap(int[] arr,int i,int j)
    {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    public void buildMaxHeap(int[] arr, int length) {
        //从n-1/2的子树开始调整
        for(int i=length-1;i>0;i--)
        {
           if(i%2==0)
           {
               //说明是右子树
               if(arr[i]<arr[(i-2)/2])
               {
                   swap(arr,i,(i-2)/2);
                   adjustDown(arr,i,length);
               }
              
           }
            else if(arr[i]<arr[(i-1)/2])
            {
                swap(arr,i,(i-1)/2);
                adjustDown(arr,i,length);
            }
            
        }
    }
   
    public void adjustDown(int[] arr, int i,int length) {
         if(i*2+1>=length-1)
         {
             return;
         }
        if(arr[i]<arr[2*i+1])
        {
            swap(arr,i,2*i+1);
        }
        if((2*i+2)<length-1&&arr[i]<arr[2*i+2])
        {
            swap(arr,i,2*i+2);
        }
        adjustDown(arr,i*2+1,length);
        adjustDown(arr,i*2+2,length);
        }
       
    
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) 
    {
//
         ArrayList<Integer> res=new ArrayList<>();
        int cur_length=input.length;
        for(int i=0;i<k;i++)
        {
            buildMaxHeap(input,cur_length);
            int temp=input[0];
            input[0]=input[cur_length-1];
            cur_length--;
            input[cur_length]=temp;//交换堆头堆尾的元素
            res.add(temp);
        }
       
        return res;
    }
   
    
}