# Partial Sort

## Setup

``````// A few Heap-functions that operate on an array
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;
}

// The main algorithm
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);
}

// Sample data & call
``````

## Test runner

Testing in
TestOps/sec
Max Heap
``````var arr = Array.from({length:20}, () => Math.floor(Math.random() * 1e5));

partialSortWithMaxHeap(arr, 3);``````
Native Sort
``````var arr = Array.from({length:20}, () => Math.floor(Math.random() * 1e5));

arr.sort();
if(arr.length > 3) {
arr.length = 3;
}
``````
``var arr = Array.from({length:20}, () => Math.floor(Math.random() * 1e5));``