heapsort.coffee

maxHeapify = (arr, i, heapSize)->
    left = i * 2 + 1
    right = i * 2 + 2
    largest = i
    if left < heapSize && arr[i] < arr[left]
        largest = left
    if right < heapSize && arr[largest] < arr[right]
        largest = right
    if largest isnt i
        temp = arr[i]
        arr[i] = arr[largest]
        arr[largest] = temp
        maxHeapify arr, largest, heapSize

buildMaxHeap = (arr)->
    lastNode = parseInt((arr.length - 1) / 2)
    for i in [lastNode..0]
        maxHeapify arr, i, arr.length
    return

heapSort = (arr)->
    return arr if arr.length < 2
    debugger
    buildMaxHeap arr
    for i in [arr.length - 1..0]
        temp = arr[i]
        arr[i] = arr[0]
        arr[0] = temp
        maxHeapify arr, 0, i
    arr

#test
console.log heapSort [1,2,3,3,4,6, 9, 2, 1]
console.log heapSort [1]
console.log heapSort [0]
console.log heapSort [1,0]
console.log heapSort [1,0,1]