#algorithm #sort

idea

Heap sort follows that:

1. make array into a Heap by heapifying it
2. Takes the largest element, swap with last, make the heap one element shorter (consider its upper bound one less)
3. siftDown the first element (i.e. put it in its right place)
4. Repeat from 2 until heap size is 1

links

Heap

references

https://www.geeksforgeeks.org/heap-sort/?ref=lbp

reference implementation

function heapify(array, root = 0) {
  if (root >= array.length / 2) {
    return
  }
  const c1 = root * 2 + 1
  const c2 = root * 2 + 2
  heapify(array, c1)
  heapify(array, c2)
  siftDown(array, root, array.length)
}

function siftDown(array, root, size) {
  let val = array[root];

  while (true) {
    const c1 = root * 2 + 1
    const c2 = root * 2 + 2
    const val1 = c1 < size ? array[c1] : Number.MIN_VALUE
    const val2 = c2 < size ? array[c2] : Number.MIN_VALUE
    if (val1 > val2 && val1 > val) {
      swap(array, root, c1)
      root = c1
    } else if (val2 > val) {
      swap(array, root, c2)
      root = c2
    } else {
      // elmt in its place
      break;
    }
  }
}

function swap(array, i, j) {
  const tmp = array[i]
  array[i] = array[j]
  array[j] = tmp
}

function heapSort(array) {
  let size = array.length
  heapify(array, 0)
  while (size > 1) {
    swap(array, 0, --size)
    siftDown(array, 0, size)
  }
}

const array = [3, 4, 1, 5, 34, 21, 454, 12, 66, 23, 34, 55, 2, 5, 6, 2, 9, 7]
heapSort(array)
console.log(array)