- 堆结构：是一棵完全二叉树；
- 大顶堆：任何一个节点>=左右子节点，堆顶是整个堆结构中的最大值；
- 小顶堆：任何一个节点<=左右子节点，堆顶是整个堆结构中的最小值。
- 自上而下构建大顶堆：假设整个数组是一个堆结构，但不是大顶堆，此时堆结构大小等于数组长度。从堆末尾数据开始向下构建大顶堆，在当前节点和其左右子节点中寻找较大值，并选择是否交换位置，交换位置后继续与其左右子节点比较，直到不用交换或者没有子节点，说明此时已经是大顶堆了。
- 自下而上插入数据构建大顶堆：待插入的数据进入到堆结构中，与其父节点比较，选择是否交换位置，交换位置后继续与父节点比较，直到不交换位置或者来到堆顶，说明此时整个堆结构就是一个大顶堆。
- 堆排序：首先需要将数组构建成大顶堆，依次将堆顶数据与堆末尾数据交换，堆尾数据来到堆顶后向下构建大顶堆，最终堆结构缩小到0，最大值被依次放入到数组末尾处。
代码：
function heapSort(arr) {
// 无效数据直接返回
if (arr == null || arr.length < 2) {
return
}
// 自下而上逐一插入数据构建大顶堆
// for (let i = 0; i < arr.length; i++) {
// heapInsert(arr, i)
// }
// 自上而下构建大顶堆 此时假设整个数组是一个堆结构 但不是大顶堆
// 从堆结构末尾数字开始向下构建大顶堆 速度较快
for (let i = arr.length - 1; i >= 0; i--) {
heapify(arr, i, arr.length)
}
// 此时整个数组经过整理已经构成大顶堆结构
// 大顶堆大小即是数组长度
let heapSize = arr.length
// 每次将堆顶数据与堆末尾数据交换 同时将堆结构大小减小
// 再从堆顶向下构建大顶堆 数组末尾就是整个数组的最大值
while (heapSize > 0) {
// 将堆顶数据依次放入数组末尾
swap(arr, 0, --heapSize)
// 从堆顶开始向下构建大顶堆
heapify(arr, 0, heapSize)
}
}
// ------------------------4个函数-----------------------------------
// ------------------------4个函数-----------------------------------
// 自上而下构建大顶堆 从当前数据开始自上而下构建大顶堆直到堆结构末尾
// 参数是当前数据索引以及堆结构的大小
function heapify(arr, i, heapSize) {
// 左子节点
let l = 2 * i + 1
// 当前节点有子节点
// 如果当前节点有子节点 必然有左子节点
while (l < heapSize) {
// 在子节点中寻找较大值索引 需要先判断是否有右子节点
let maxIndex = l + 1 < heapSize && arr[l + 1] > arr[l] ? (l + 1) : l
// 在较大子节点和当前节点中寻找较大值索引
maxIndex = arr[i] > arr[maxIndex] ? i : maxIndex
// 当前节点是较大值时 已经构成大顶堆 不需要再继续向下构建大顶堆
if (i == maxIndex) {
break
}
// 当前节点不是较大值时 当前值和较大值互换
swap(arr, i, maxIndex)
// 指向当前数的指针向下移动 继续向下构建大顶堆
i = maxIndex
// 更新左子节点
l = 2 * i + 1
}
}
// ------------------------4个函数-----------------------------------
// ------------------------4个函数-----------------------------------
// 自下而上逐一向大顶堆中插入数据
// 参数是待插入数据
function heapInsert(arr, i) {
// 当前数插入到大顶堆后的父节点指针
// 此时整个堆结构由于插入了新数据 不一定是大顶堆
let f = Math.floor((i - 1) / 2)
// 当待插入数据(当前数)大于其父节点时 持续向上移动 直到到达堆顶停止
while (arr[i] > arr[f]) {
// 当前数与父节点交换
swap(arr, i, f)
// 当前数指针向上移动
i = f
// 更新父节点指针
f = Math.floor(( i - 1) / 2)
}
}
// ------------------------4个函数-----------------------------------
// ------------------------4个函数-----------------------------------
function swap(arr, i, j) {
let tmp = arr[i]
arr[i] = arr[j]
arr[j] = tmp
}
性能：
- 时间复杂度：长期期望是O(N*log N)
- 空间复杂度：O(1)
- 稳定性：无法保持，在构建大顶堆的过程中稳定性被破坏了
