// 交换
function swap(arr, a, b) {
    if (a == b) { return; }
    var c = arr[a];
    arr[a] = arr[b];
    arr[b] = c;
}

// 堆排序
function heapSort(arr) {
    let n = arr.length;
    if(n <= 1){
        return arr;
    }
    buildHeap(arr);
    
    // 堆排序
    for(var i = n - 1 ; i > 0; i -- ){
        swap(arr, 0, i);
        maxHeapify(arr, 0, i)
    }
    return arr;
}

// 构建堆
function buildHeap(arr){
    var n = arr.length;
    var lastNode = n - 1;
    var parent = Math.floor((lastNode - 1) / 2);
    for(var i = parent; i >= 0; i --){
        maxHeapify(arr, i, n);
    }
    return arr
}

// 最大堆调整
function maxHeapify(arr, i, n) {
    if( i > n){
        return;
    }
    var left = 2 * i + 1;
    var right = 2 * i + 2; 
    var max = i;
    if(arr[left] > arr[max] && left < n){
        max = left;
    }
    if(arr[right] > arr[max] && right < n){
        max = right;
    }

    if(max !== i){
        swap(arr,i,max);
        maxHeapify(arr, max, n);
    }
}

console.log('heapSort([5, 2, 4, 6, 1, 3]); ',heapSort([5, 2, 4, 6, 1, 3]))