[8,9,10,4,1,2,5,6,8,7,1]
结果
[9, 8, 10, 8, 7, 2, 5, 6, 4, 1, 1]
最大值终将在最左侧
function maxHeap (arr) {
// 找到中间偏小位置树立标杆
let st = Math.floor(arr.length / 2 - 1)
// [0,1,2,3,4,5,6,7,8,9]
// 从标杆位置遍历执行排序
for (let i = st; i >= 0; i--) {
sortMax(arr, i)
console.log(arr)
}
console.log(arr)
// 排序方法
function sortMax (arr, i) {
console.log(i)
// 建立左侧值
let left = i * 2 + 1
// 建立右侧值
let right = i * 2 + 2
// 定义最大值下标
let max = i
// 判断左侧值是否存在，并且比默认值大
if (arr[left] && arr[left] > arr[max]) {
// 将最大值下标修改为left
max = left
}
// 判断右侧值是否存在，是否比当前最大值大
if (arr[right] && arr[right] > arr[max]) {
// 将最大值下标修改为right
max = right
}
// 如果最大值下标不是默认下标，将值替换
if (max != i) {
let s = arr[max]
arr[max] = arr[i]
arr[i] = s
// 不能判断max是不是最大分支时
sortMax(arr, max)
}
}
}
