heapSort.js

function createHeap (arr) {
  var startIndex = Math.floor(arr.length / 2) - 1

  while(startIndex >= 0) {
    heapify(arr, startIndex)
    startIndex -= 1
  }
  return arr
}


function heapify (arr, startIndex) {
   var leftChild = arr[2 * startIndex + 1]
   var rightChild = arr[2 * startIndex + 2]
   var temp = arr[startIndex]

  // leaf node
  if (!leftChild && !rightChild) {
    return
  }

  // right most node on n-1 level
  if (!rightChild) {
    if (leftChild < temp) {
      arr[startIndex] = leftChild
      arr[2 * startIndex + 1] = temp
    }
    return
  }


   if (arr[startIndex] < leftChild && arr[startIndex] < rightChild) {
     return
   }

   var temp = arr[startIndex]
   if (leftChild < rightChild) {
     arr[startIndex] = leftChild
     arr[2 * startIndex + 1] = temp
     heapify(arr, 2 * startIndex + 1)
   } else {
     arr[startIndex] = rightChild
     arr[2 * startIndex + 2] = temp
     heapify(arr, 2 * startIndex + 2)
   }
}



function heapSort (arr) {
  createHeap(arr)
  var sortedArr = []
  var end = arr.length
  for(var i=1; i <= end; i++) {
    var temp = arr[0]
    arr[0] = arr[arr.length-1]
    arr[arr.length-1] = temp
    sortedArr.push(temp)
    arr.pop()
    heapify(arr, 0)
  }
  return sortedArr
}