public class Solution {
  public int[] kSmallest(int[] array, int k) {
    // Write your solution here
    if (array == null) {
      return array;
    } else if (array.length == 0 || k == 0) {
      return new int[0];
    }
    Queue<Integer> maxHeap = new PriorityQueue<>(k, new myComparator());
    for (int i = 0; i < array.length; i++) {
      if (i < k) {
        maxHeap.offer(array[i]);
      } else {
        if (array[i] < maxHeap.peek()) {
          maxHeap.poll();
          maxHeap.offer(array[i]);
        }
      }
    }

    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i--) {
      result[i] = maxHeap.poll();
    }
    return result;
  }
}

class myComparator implements Comparator<Integer> {
  @Override
  public int compare(Integer o1, Integer o2) {
    if (o1.equals(o2)) {
      return 0;
    }
    return o1 > o2 ? -1 : 1;
  }
}

assumption: array is not null, k > 0 and <= array.length

approach : build a maxHeap and offer first k elements. and iterate least elements, if the element < maxHeap.peek(), then, maxHeap poll() and offer this element, after iterate the whole array, the maxHeap store the k smallest elements.

Time: O(k) for heapify k element, and O((n - k) logk 的poll and offer. So, time com: O(k + (n-k)logk)

use additional array[] to store the results.