자바 토 크 문제 최대 더미 실현

제목 설명:
n 개의 정 수 를 입력 하여 그 중에서 가장 작은 K 개 수 를 찾 아 라.예 를 들 어 4, 5, 1, 6, 2, 7, 3, 8 이라는 8 개의 숫자 를 입력 하면 가장 작은 4 개의 숫자 는 1, 2, 3, 4 이다.

import java.util.*;
public class Solution {
    public ArrayList GetLeastNumbers_Solution(int [] input, int k) {
          ArrayListtopk=new ArrayList();
        if(k>input.length){
        return topk;
        }
        buildMaxHeap(input,k);
        for(int i=k;i0        ，    k-1 （             ）    
    private void buildMaxHeap(int []input ,int k){
        for(int i=k/2;i>=0;i--)
            heapify(input,i,k);
    }
    
    //First  Step:  index         ，        
    private void heapify(int[]input,int index,int k){
        int left=((index+1)<<1)-1;   //     ：（       0  ，   1  ）
        int right=left+1;//     
        int largest=index;//             index
        if(leftinput[largest])//       largest    
            largest=left;
        if(rightinput[largest])//       largest    
            largest=right;
        if(largest==index)return;//index     ，  index            
        //  ，  ，            
        int temp = input[index];
        input[index]=input[largest];
        input[largest]=temp;
        heapify(input,largest,k);
        
    }
}