x-note
Search…
堆排序
堆排序(Heapsort)就是把最大(小)堆的最大(小)数取出,然后继续将剩余的元素重新构建最大(小)堆,直到剩余数只有一个时结束。
最大堆:最大堆中的最大元素值出现在根结点(堆顶),堆中每个父节点的元素值都大于等于其孩子结点(如果存在) 最小堆:最小堆中的最小元素值出现在根结点(堆顶),堆中每个父节点的元素值都小于等于其孩子结点(如果存在)
  • 平均时间复杂度:
    O(nlog2n)\mathcal{O}({n}\log_{2}{n})
  • 最好时间复杂度:
    O(nlog2n)\mathcal{O}({n}\log_{2}{n})
  • 最坏时间复杂度:
    O(nlog2n)\mathcal{O}({n}\log_{2}{n})
  • 空间复杂度:
    O(1)\mathcal{O}(1)
    ,最大为
    O(n)\mathcal{O}(n)
  • 稳定性:不稳定
  • 排序方式:原地(in-place)
堆(二叉堆)是一种近似于完全二叉树的结构,这使得堆可以利用数组来表示。
Could not load image
仔细观察能够轻易地出父节点与其孩子节点的下标之间的关系:
  • 节点 i 的父节点坐标:
    Parent(i)=floor(i12)Parent(i) = floor(\dfrac{i - 1}{2})
  • 节点 i 的左节点坐标:
    Left(i)=2i+1Left(i) = 2i + 1
  • 节点 i 的右节点坐标:
    Right(i)=2(i+1)Right(i) = 2(i + 1)
完全二叉树,在不考虑二叉树最后一层的情况下,其余层的节点都是满的。也就是说,具有 n 个节点的完全二叉树的深度为
k=log2n+1k = log_{2}n + 1
,深度为 k 的完全二叉树至少有
2k{2}^{k}
个节点,至多有
2k+1{2}^{k + 1}
个节点。
一般实现:
/*
* 数组元素交换函数
*/
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;
}
Copy link