x-note
Search…
堆排序
堆排序（Heapsort）就是把最大（小）堆的最大（小）数取出，然后继续将剩余的元素重新构建最大（小）堆，直到剩余数只有一个时结束。
最大堆：最大堆中的最大元素值出现在根结点（堆顶），堆中每个父节点的元素值都大于等于其孩子结点（如果存在） 最小堆：最小堆中的最小元素值出现在根结点（堆顶），堆中每个父节点的元素值都小于等于其孩子结点（如果存在）
- 平均时间复杂度：
- 最好时间复杂度：
- 最坏时间复杂度：
- 空间复杂度：，最大为
- 稳定性：不稳定
- 排序方式：原地（in-place）
堆（二叉堆）是一种近似于完全二叉树的结构，这使得堆可以利用数组来表示。
Could not load image
仔细观察能够轻易地出父节点与其孩子节点的下标之间的关系：
- 节点 i 的父节点坐标：
- 节点 i 的左节点坐标：
- 节点 i 的右节点坐标：
完全二叉树，在不考虑二叉树最后一层的情况下，其余层的节点都是满的。也就是说，具有 n 个节点的完全二叉树的深度为，深度为 k 的完全二叉树至少有个节点，至多有个节点。
一般实现：
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!
Last modified 3yr ago
Copy link