题解 | #最小的K个数#

堆排序实现： 容量不足：在最后插入元素+ 自下而上 容量满：对比是否小于堆顶元素：小于->替换堆顶元素+自上而下堆化

import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> list = new ArrayList();
        if(k<=0){
            return list;
        }
        if(input==null || input.length<=0){
            return list;
        }
        if(input.length<k){
            for(int i=0;i<input.length;++i){
                list.add(input[i]);
            }
            return list;
        }
        HeapMaxTop heapM = new HeapMaxTop(k);
        for(int i=0;i<input.length;++i){
            heapM.insert(input[i]);
        }
        return heapM.toList();
    }
    
    public class HeapMaxTop {
        //first pass
        private final int[] data;
        private final int capacity;
        private int count;
        
        public HeapMaxTop(int capacity){
            this.capacity = capacity>0?capacity:1;
            this.data = new int[this.capacity+1];
        }
        
        public ArrayList<Integer> toList(){
            ArrayList<Integer> list = new ArrayList();
            for(int i=1;i<=count;i++){
                list.add(data[i]);
            }
            return list;
        }
        
        public boolean isFull(){
            return count >= capacity;
        } 
        /**
        *插入 或 替换
        */
        public void insert(int val){
            if(isFull()){
                if(val < data[1]){
                    data[1]=val;
                    heapify(1);
                }
                return;
            }
            count++;
            data[count]=val;
            //自下而上
            int i = count;
            while(i/2 >0 && data[i]>data[i/2]){
                swap(i,i/2);
                i=i/2;
            }
        }
        /**
        * 自上而下
        */
        private void heapify(int i){
            while(i<=count){
                int maxPos = i;
                int left = i*2;
                if(left<=count && data[left]>data[maxPos]){
                    maxPos = i*2;
                }
                int right = i*2+1;
                if(right<=count && data[right]>data[maxPos]){
                    maxPos = right;
                }
                if(maxPos == i){
                    break;
                }
                swap(maxPos,i);
                i = maxPos;
            }
        }
        
        private void swap(int i,int j){
            int temp = data[i];
            data[i] = data[j];
            data[j] = temp;
        }
        
    }
}