52 52
12 5 12 5
79 55 24 15 15 62 38 “当前”层→ 79
36 16 62 12 38 36 16 55 12 24
0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 2 3 4 5 6 7 8 9 10 11 12 52 12 5 79 55 24 15 36 16 62 12 38 52 12 5 79 62 38 15 36 16 55 12 24
(a) 原始堆树 (b) 调整“当前”层子树为
调整时从24开始，然后是55，79，? 三个子堆；38↑，62↑，79为根
图5.7.6 初始化堆过程
52 “当前”层→ 79
38 62 38 “当前”层→ 79
15 15 36 62 24 36 55 24
16 16 12 55 12 5 12 52 12 5
0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 2 3 4 5 6 7 8 9 10 11 12 79 62 38 36 55 24 15 12 16 52 12 5 52 79 38 36 62 24 15 12 16 55 12 5
(c) 调整“当前”层子树为 (d) 调整“当前”层子树为
二个子堆； 38↑，79↑为根 最后堆；79↑为根
图5.7.6 初始化堆过程
52 “当前”层→ 79 38 62 38 “当前”层→ 79 15 15 36 62 24 36 55 24 16 16 12 55 12 5 12 52 12 5 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 2 3 4 5 6 7 8 9 10 11 12 52 79 38 36 62 24 15 12 16 55 12 5 79 62 38 36 55 24 15 12 16 52 12 5
(d) 调整“当前”层子树为
(e) 调整“当前”层子树为
最后堆；79↑为根
二个子堆； 38↑，79↑为根
图5.7.6 初始化堆过程
堆排序
堆排序的过程，是利用删除堆顶结点来完成的。堆顶结点是整个堆中最大的一个结点，删除它的同时，将它移到另一个结果存储区中存放，然后，再将删除堆顶后的堆重新调整为一个堆。如果重复删除，移至结果区下一个存储空间存储，直到堆中的所有结点被全部删除，最后在结果存储区中的数据就是按从大至小地排列。
79 62
62 38 56 38
15 15 56 55 24 52 55 24
16 16 52 12 52 12 79
0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 79 62 38 56 55 24 15 12 16 52 52 62 56 38 52 55 24 15 12 16 79
(a) 原始堆 (b) 第一个堆顶移下
56 55
55 38 52 38
15 15 52 16 24 12 16 24
62 16 62 12 12 79 56 79
0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 16 56 55 38 52 16 24 15 12 62 79 12 55 52 38 12 16 24 15 56 62 79
(c) 第二个堆顶移下 (d) 第三个堆顶移下
图5.7.9 三个堆顶移下排序的过程
堆排序比较次数据为O（nlog2n）