Heap Sort and Streaming Data

function heapSort(items) {
  const n = items.length

  // Phase 1: turn the array into a max-heap, in place. O(n).
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    siftDown(items, i, n)
  }

  // Phase 2: swap the largest to the end, shrink, repair. O(n log n).
  for (let end = n - 1; end > 0; end--) {
    ;[items[0], items[end]] = [items[end], items[0]]
    siftDown(items, 0, end)
  }

  return items
}

function siftDown(items, i, limit) {
  while (true) {
    const left = 2 * i + 1
    const right = 2 * i + 2
    let largest = i

    if (left < limit && items[left] > items[largest]) largest = left
    if (right < limit && items[right] > items[largest]) largest = right
    if (largest === i) break

    ;[items[i], items[largest]] = [items[largest], items[i]]
    i = largest
  }
}

console.log(heapSort([5, 3, 8, 1, 9, 2]))  // [1, 2, 3, 5, 8, 9]