// https://stackoverflow.com/q/15621145/5459839
function bisect(items, x, lo, hi) {
  var mid;
  if (typeof(lo) == 'undefined') lo = 0;
  if (typeof(hi) == 'undefined') hi = items.length;
  while (lo < hi) {
    mid = Math.floor((lo + hi) / 2);
    if (x < items[mid]) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

function insort(items, x) {
  items.splice(bisect(items, x), 0, x);
}

function partialSort(items, k) {
  var smallest = [];
  for (var i = 0, len = items.length; i < len; ++i) {
    var item = items[i];
    if (smallest.length < k || item < smallest[smallest.length - 1]) {
      insort(smallest, item);
      if (smallest.length > k)
        smallest.splice(k, 1);
    }
  }
  return smallest;
}
    
// Bergi's improvement
function partialSortBergi(items, k) {
    var smallest = items.slice(0, k).sort(),
        max = smallest[k-1];
    for (var i = k, len = items.length; i < len; ++i) {
        var item = items[i];
        if (item < max) {
            insort(smallest, item);
            smallest.length = k;
            max = smallest[k-1];
        }
    }
    return smallest;
}

// Trincot's MaxHeap based solution
function maxSiftDown(arr, i=0, value=arr[i]) {
    if (i >= arr.length) return;
    while (true) {
        var j = i*2+1;
        if (j+1 < arr.length && arr[j] < arr[j+1]) j++;
        if (j >= arr.length || value >= arr[j]) break;
        arr[i] = arr[j];
        i = j;
    }
    arr[i] = value;
}

function maxHeapify(arr) {
    for (var i = arr.length>>1; i--; ) maxSiftDown(arr, i);
    return arr;
}

function partialSortWithMaxHeap(items, k) {
    var heap = maxHeapify(items.slice(0, k));
    for (var i = k, len = items.length; i < len; ++i) {
        var item = items[i];
        if (item < heap[0]) maxSiftDown(heap, 0, item);
    }
    return heap.sort((a,b) => a-b);
}

let arr = Array.from({length:5000}, () => Math.floor(Math.random() * 1e5));
let k = 10;