堆排序
**堆排序(Heapsort)**就是把最大(小)堆的最大(小)数取出,然后继续将剩余的元素重新构建最大(小)堆,直到剩余数只有一个时结束。
最大堆:最大堆中的最大元素值出现在根结点(堆顶),堆中每个父节点的元素值都大于等于其孩子结点(如果存在) 最小堆:最小堆中的最小元素值出现在根结点(堆顶),堆中每个父节点的元素值都小于等于其孩子结点(如果存在)
平均时间复杂度:
最好时间复杂度:
最坏时间复杂度:
空间复杂度:,最大为
稳定性:不稳定
排序方式:原地(in-place)
堆(二叉堆)是一种近似于完全二叉树的结构,这使得堆可以利用数组来表示。

仔细观察能够轻易地出父节点与其孩子节点的下标之间的关系:
节点 i 的父节点坐标:
节点 i 的左节点坐标:
节点 i 的右节点坐标:
完全二叉树,在不考虑二叉树最后一层的情况下,其余层的节点都是满的。也就是说,具有 n 个节点的完全二叉树的深度为 ,深度为 k 的完全二叉树至少有 个节点,至多有 个节点。
一般实现:
/*
* 数组元素交换函数
*/
function swap(arr, i, j){
let tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
function heapSort(arr) {
buildMaxHeap(arr);
for (let i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
maxHeapify(arr, 0, i);
}
/**
* 构建最大堆
**/
function buildMaxHeap(arr) {
const heapSize = arr.length;
let iParent = (heapSize - 1) >> 1; // Math.floor((heapSize - 1) / 2);
for (let i = iParent; i >= 0; --i) {
maxHeapify(arr, i, heapSize);
}
}
/**
* 从 index 开始检查并保持最大堆性质
**/
function maxHeapify(arr, index, heapSize) {
let iMax = index,
iLeft = 2 * index + 1,
iRight = 2 * (index + 1);
if (iLeft < heapSize && arr[index] < arr[iLeft]) {
iMax = iLeft;
}
if (iRight < heapSize && arr[iMax] < arr[iRight]) {
iMax = iRight;
}
if (iMax != index) {
swap(arr, iMax, index);
maxHeapify(arr, iMax, heapSize); // 递归调整
}
}
return arr;
}
最后更新于