import java.util.ArrayList;
import java.util.Arrays;

public class Solution {

    public void insert(ArrayList<Integer> heap, int val){
        heap.add(val);
        update(heap, heap.size()-1);
    }

    private void update(ArrayList<Integer> heap, int index){
        if(index==1){
            return;
        }
        if(heap.get(index)<heap.get(index/2)){
            int temp = heap.get(index);
            heap.set(index, heap.get(index/2));
            heap.set(index/2, temp);
            update(heap, index/2);
        }
    }

    public void delete(ArrayList<Integer> heap){
        if(heap.size()<=1){
            return;
        }
        int temp = heap.get(1);
        heap.set(1, heap.get(heap.size()-1));
        heap.set(heap.size()-1, temp);
        heap.remove(heap.size()-1);
        heapify(heap, 1);
    }

    private void heapify(ArrayList<Integer> heap, int index){
        if(index>(heap.size()-1)/2){
            return;
        }
        int indexMin;
        if(index*2==heap.size()-1){
            indexMin = index*2;
        }else{
            indexMin = heap.get(index*2)<heap.get(index*2+1)?index*2:index*2+1;
        }
        if(heap.get(index)>heap.get(indexMin)){
            int temp = heap.get(index);
            heap.set(index, heap.get(indexMin));
            heap.set(indexMin, temp);
            heapify(heap, indexMin);
        }
    }

    public ArrayList<Integer> generateHeap(int[] array){
        ArrayList<Integer> heap = new ArrayList<>();
        heap.add(-1);
        for(int i=0;i<array.length;i++){
            insert(heap, array[i]);
        }
        return heap;
    }

    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if(k>input.length){
            ArrayList<Integer> list = new ArrayList<>();
            return list;
        }
        ArrayList<Integer> heap = generateHeap(input);
        ArrayList<Integer> result = new ArrayList<>();
        for(int i=0;i<k;i++){
            result.add(heap.get(1));
            delete(heap);
        }
        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] array = {4,5,1,6,2,7,3,8};
        ArrayList list = solution.GetLeastNumbers_Solution(array, 10);
        System.out.println();
    }
}