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}
个节点。
一般实现:
1
/*
2
* 数组元素交换函数
3
*/
4
function swap(arr, i, j){
5
let tmp = arr[i];
6
arr[i] = arr[j];
7
arr[j] = tmp;
8
}
9
10
function heapSort(arr) {
11
buildMaxHeap(arr);
12
for (let i = arr.length - 1; i > 0; i--) {
13
swap(arr, 0, i);
14
maxHeapify(arr, 0, i);
15
}
16
17
/**
18
* 构建最大堆
19
**/
20
function buildMaxHeap(arr) {
21
const heapSize = arr.length;
22
let iParent = (heapSize - 1) >> 1; // Math.floor((heapSize - 1) / 2);
23
for (let i = iParent; i >= 0; --i) {
24
maxHeapify(arr, i, heapSize);
25
}
26
}
27
28
/**
29
* 从 index 开始检查并保持最大堆性质
30
**/
31
function maxHeapify(arr, index, heapSize) {
32
let iMax = index,
33
iLeft = 2 * index + 1,
34
iRight = 2 * (index + 1);
35
if (iLeft < heapSize && arr[index] < arr[iLeft]) {
36
iMax = iLeft;
37
}
38
if (iRight < heapSize && arr[iMax] < arr[iRight]) {
39
iMax = iRight;
40
}
41
if (iMax != index) {
42
swap(arr, iMax, index);
43
maxHeapify(arr, iMax, heapSize); // 递归调整
44
}
45
}
46
return arr;
47
}
Copied!
Copy link