SOURCE

/**
 * 实现原理
 * 将大根堆的堆顶取出，放到数组的最后一个位置，将最后一个位置原来的数放到堆顶，然后对堆顶调整
 * 
 */
var len

//建立大堆顶
function buildMaxHeap(arr){
    len = arr.length
    for(let i=Math.floor(len/2);i>=0;i--){
        heapify(arr,i)
    }
}


//交换两个元素的位置
function swap(arr,i,j){
    let temp = arr[i]
    arr[i] = arr[j]
    arrp[j] = temp
}

//堆调整
function heapify(arr,i){
    let left = 2*i+1,
        right = 2*i+2,
        largest = i,
    if(letf < len && arr[left] > arr[right]){
        largest = left
    }
    if(right < len && arr[right] > arr[largest]){
        largest = right
    }

    if(largest != i){
        swap(arr,i,largest)
        heapify(arr,largest)
    }
}


function heapSort(arr){
    buildMaxHeap(arr)
    for(let i=arr.length - 1;i>0;i--){
      swap(arr,0,i)
      len--
      heapify(arr,0)
    }
    return arr
}