堆：孩子节点总是小于（或大于）父节点的完全二叉树 时间复杂度：O(nlogn) 步骤：
- 堆调整：比较二叉树内部节点与其孩子节点大小，将最大节点与内部节点交换，并递归对交换的孩子节点执行堆调整
- 创建堆（从完全二叉树最后一个内部节点向前执行堆调整）
- 交换堆首位，堆尺寸-1
- 对新堆的堆首执行堆调整
- 重复执行第三步直到堆尺寸为0
// 初始化数据
var numbers = [];
for (var i = 0; i < 20; i ) {
numbers.push(Math.floor(Math.random() * 100));
}
console.log(JSON.stringify(numbers))
function swap(numbers, i, j) {
var temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
// 堆调整
function heapAdjust(numbers, point, size) {
if (point >= size / 2) {
return;
}
// 将内部节点与最大的孩子节点交换
var leftp = point * 2,
rightp = leftp 1,
largestp = point;
if (numbers[leftp] > numbers[largestp]) {
largestp = leftp;
}
if (rightp < size && numbers[rightp] > numbers[largestp]) {
largestp = rightp;
}
if (largestp != point) {
swap(numbers, largestp, point);
// 如果发生交换，孩子节点可能不再满足堆特性，对孩子节点重新进行递归堆调整
heapAdjust(numbers, largestp, size);
}
}
// 创建最大堆
for (var i = Math.floor(numbers.length / 2); i >= 0; i--) {
// 从最后一个内部节点开始堆调整
heapAdjust(numbers, i, numbers.length);
}
console.log(JSON.stringify(numbers))
// 排序输出
for (var i = numbers.length - 1; i >= 0; i--) {
// 最大值放到数组末尾后，对新的堆顶进行调整
swap(numbers, 0, i);
heapAdjust(numbers, 0, i);
}
console.log(JSON.stringify(numbers))[56,61,18,86,13,72,31,75,76,56,21,87,71,68,99,10,51,11,55,32] [99,87,76,86,56,72,71,75,51,56,21,18,31,68,61,10,13,11,55,32] [10,11,13,18,21,31,32,51,55,56,56,61,68,71,72,75,76,86,87,99]
