堆排序解析及JavaScript实现

什么是堆

在计算机科学中,二叉树(英语:Binary tree)是每个节点最多只有两个分支(不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”和“右子树”。二叉树的分支具有左右次序,不能颠倒。

二叉树的每个结点至多只有二棵子树(不存在度大于 2 的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第 i 层至多有 2i - 1 个结点;深度为 k 的二叉树至多有 2k - 1 个结点;对任何一棵二叉树 T,如果其终端结点数为 n0,度为 2 的结点数为 n2,则n0 = n2 + 1

二叉树又分为完全二叉树(complete binary tree)和满二叉树(full binary tree)

满二叉树:一棵深度为 k,且有 2k - 1 个节点称之为满二叉树

完全二叉树:深度为 k,有 n 个节点的二叉树,当且仅当其每一个节点都与深度为 k 的满二叉树中序号为 1n 的节点对应时,称之为完全二叉树。

堆排序

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

通常堆是通过一维数组来实现的,在数组起始位置为0的情形中:

  • Parent(i) = floor((i-1)/2)i 的父节点下标
  • Left(i) = 2i + 1i 的左子节点下标
  • Right(i) = 2(i + 1)i 的右子节点下标

堆排序步骤

最大堆调整

  1. 初始化,i从最后一个父节点开始调整
  2. 建立父节点下标和子节点下标
  3. 先比较两个子节点大小,选择最大的
  4. 如果父节点小宇子节点时,交换父子內容再继续子节点和孙节点比较
  5. 先将第一个元素和已排好元素前一位做交换,再从新调整,直到排序完毕

流程图

堆排序流程图

JavaScript代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function heapSort(arr) {
// 交换函数
function swap(i, j) {
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
function max_heapify(start, end) {
//建立父节点下标和子节点下标
var dad = start;
var son = dad * 2 + 1;
if (son >= end)//若子节点下标超过范围直接跳出函数
return;
if (son + 1 < end && arr[son] < arr[son + 1])//先比较两个子节点大小,选择最大的
son++;
if (arr[dad] <= arr[son]) {//如果父节点小于子节点时,交换父子內容再继续子节点和孙节点比较
swap(dad, son);
max_heapify(son, end);
}
}
var len = arr.length;
//初始化,i从最后一个父节点开始调整
for (var i = Math.floor(len / 2) - 1; i >= 0; i--){
max_heapify(i, len);
}
// 先将第一个元素和已排好元素前一位做交换,再从新调整,直到排序完毕
for (var i = len - 1; i > 0; i--) {
swap(0, i);
max_heapify(0, i);
}
return arr;
}

验证

1
2
heapSort([15, 23, 14, 26, 14, 85, 17, 12, 3, 18, 45, 96, 7, 74, 45, 15, 12, 26, 12, 53]);
// 输出 [3, 7, 12, 12, 12, 14, 14, 15, 15, 17, 18, 23, 26, 26, 45, 45, 53, 74, 85, 96]

参考内容