k sort in javascript

index.tsx
function kSort(arr, k) {
  const heap = [];

  // function to heapify up (min heap)
  function heapifyUp(index) {
    const parent = Math.floor((index - 1) / 2);
    if (parent >= 0 && heap[index] < heap[parent]) {
      swap(index, parent);
      heapifyUp(parent);
    }
  }

  // function to heapify down (min heap)
  function heapifyDown(index) {
    const left = 2 * index + 1;
    const right = 2 * index + 2;
    let smallest = index;

    if (left < heap.length && heap[left] < heap[smallest]) {
      smallest = left;
    }

    if (right < heap.length && heap[right] < heap[smallest]) {
      smallest = right;
    }

    if (smallest !== index) {
      swap(index, smallest);
      heapifyDown(smallest);
    }
  }

  // helper function to swap elements in the heap
  function swap(a, b) {
    const temp = heap[a];
    heap[a] = heap[b];
    heap[b] = temp;
  }

  // initialize the heap with first k+1 elements
  for (let i = 0; i <= k; i++) {
    heap.push(arr[i]);
    heapifyUp(heap.length - 1);
  }

  // traverse the remaining elements and sort them
  for (let i = k + 1; i < arr.length; i++) {
    console.log(heap[0]); // print the minimum element
    heap[0] = arr[i]; // replace root with next element from array
    heapifyDown(0); // re-heapify the heap
  }

  // print the remaining elements in the heap
  while (heap.length > 0) {
    console.log(heap[0]);
    heap[0] = heap.pop();
    heapifyDown(0);
  }
}

// example usage
const arr = [6, 5, 3, 2, 8, 10, 9];
const k = 3;
kSort(arr, k); // will print: 2 3 5 6 8 9 10
1547 chars
65 lines