前言
堆排序在面试中是经常会问到的，特别是应届毕业生找工作时，面试官最喜欢问这个了。当年百度二面的时候，也被这个算法给刷了，因为像我这种不入流的大学，平时所学习的算法只是讲讲基本原理，却没有真正要求动手去实现，因此到真正需要应用的时候，根本就不懂如何去应用。
今天，在回忆、学习完堆排序的相关知识后，希望通过写下本篇文章，将所有的理论知识使用笔者的语言来表达出来，希望能够让大家更容易理解和吸收。
基础知识
我们通常所说的堆是指二叉堆，二叉堆又称完全二叉树或者叫近似完全二叉树。二叉堆又分为最大堆和最小堆。
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。数组可以根据索引直接获取元素，时间复杂度为O（1），也就是常量，因此对于取值效率极高。
最大堆的特性如下：
- 父结点的键值总是大于或者等于任何一个子节点的键值
- 每个结点的左子树和右子树都是一个最大堆
最小堆的特性如下：
- 父结点的键值总是小于或者等于任何一个子节点的键值
- 每个结点的左子树和右子树都是一个最小堆
算法思想
最大堆的算法思想是：
- 先将初始的R[0…n-1]建立成最大堆，此时是无序堆，而堆顶是最大元素
- 再将堆顶R[0]和无序区的最后一个记录R[n-1]交换，由此得到新的无序区R[0…n-2]和有序区R[n-1]，且满足R[0…n-2].keys ≤ R[n-1].key
- 由于交换后，前R[0…n-2]可能不满足最大堆的性质，因此再调整前R[0…n-2]为最大堆，直到只有R[0]最后一个元素才调整完成。
最大堆排序完成后，其实是升序序列，每次调整堆都是要得到最大的一个元素，然后与当前堆的最后一个元素交换，因此最后所得到的序列是升序序列。
最小堆的算法思想是：
- 先将初始的R[0…n-1]建立成最小堆，此时是无序堆，而堆顶元素是最小的元素
- 再将堆顶R[0]与无序区的最后一个R[n-1]交换，由此得到新的无序堆R[0…n-2]和有序堆R[n-1]，且满足R[0…n-2].keys >= R[n-1].key
- 由于交换后，前R[0…n-2]可能不满足最小堆的性质，因此再调整前R[0…n-2]为最小堆，直到只有R[0]最后一个元素才调整完成
最小堆排序完成后，其实是降序序列，每次调整堆都是要得到最小的一个元素，然后与当前无序堆的最后一个元素交换，所以所得到的序列是降序的。
提示：堆排序的过程，其实就是不断地扩大有序区，然后不断地缩小无序区，直到只有有序区的过程。
排序过程分析
因为算法比较抽象，这里直接通过举个小例子来说明堆排序的过程是如何的。下面我们用这个无序序列采用最大堆的进行堆排序，所得到的序列就是升序序列（ASC）。
无序序列：89,-7,999,-89,7,0,-888,7,-7
第一步：初始化建成最大堆：
第二步：将堆顶最大元素999与无序区的最后一个元素交换，使999成为有序区。交换后，-7成为堆顶，由于-7并不是无序区中最大的元素，因此需要调整无序区，使无序区中最大值89成为堆顶，所以-7与89交换。交换后导致89的右子树不满足最大堆的性质，因此要对右子树调整成最大堆，所以-7要与0交换，如下图：
从图中看到，当-7成89交换后，堆顶是最大元素了，但是-7的左孩子是0，右孩子是-888，由于-7<0，导致-7这个结点不满足堆的性质，因此需要调整它。所以，0与-7交换。
然后不断重复着第二步的过程，直到全部成为有序区。
最后：所得到的是升序序列
时间复杂度
堆排序的时间，主要由建立初始堆和反复调整堆这两部分的时间开销构成.由于堆排序是不稳定的，它得扭到的时间复杂度会根据实际情况较大，因此只能取平均时间复杂度。
平均时间复杂度为：O( N * log2(N) )
堆排序耗时的操作有：初始堆 + 反复调整堆，时间复杂度如下：
- 初始建堆：每个父节点会和左右子节点进行最多2次比较和1次交换，所以复杂度跟父节点个数有关。根据2x <= n（x为n个元素可以折半的次数，也就是父节点个数），得出x = log2n。即O ( log2n )
- 反复调整堆：由于初始化堆过程中，会记录数组比较结果，所以堆排序对原序列的数组顺序并不敏感，最好情况和最坏情况差不多。需要抽取 n-1 次堆顶元素，每次取堆顶元素都需要重建堆（O(重建堆) < O(初始堆)）。所以小于 O(n-1) * O(log2n)
使用建议：
由于初始化堆需要比较的次数较多，因此，堆排序比较适合于数据量非常大的场合（百万数据或更多）。由于高效的快速排序是基于递归实现的，所以在数据量非常大时会发生堆栈溢出错误。
C语言实现
基于最大堆实现升序排序
|
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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
// 初始化堆 void initHeap(int a[], int len) { // 从完全二叉树最后一个非子节点开始 // 在数组中第一个元素的索引是0 // 第n个元素的左孩子为2n+1，右孩子为2n+2， // 最后一个非子节点位置在(n - 1) / 2 for (int i = (len - 1) / 2; i >= 0; --i) { adjustMaxHeap(a, len, i); } }
void adjustMaxHeap(int a[], int len, int parentNodeIndex) { // 若只有一个元素，那么只能是堆顶元素，也没有必要再排序了 if (len <= 1) { return; }
// 记录比父节点大的左孩子或者右孩子的索引 int targetIndex = -1;
// 获取左、右孩子的索引 int leftChildIndex = 2 * parentNodeIndex + 1; int rightChildIndex = 2 * parentNodeIndex + 2;
// 没有左孩子 if (leftChildIndex >= len) { return; }
// 有左孩子，但是没有右孩子 if (rightChildIndex >= len) { targetIndex = leftChildIndex; } // 有左孩子和右孩子 else { // 取左、右孩子两者中最大的一个 targetIndex = a[leftChildIndex] > a[rightChildIndex] ? leftChildIndex : rightChildIndex; }
// 只有孩子比父节点的值还要大，才需要交换 if (a[targetIndex] > a[parentNodeIndex]) { int temp = a[targetIndex];
a[targetIndex] = a[parentNodeIndex]; a[parentNodeIndex] = temp;
// 交换完成后，有可能会导致a[targetIndex]结点所形成的子树不满足堆的条件， // 若不满足堆的条件，则调整之使之也成为堆 adjustMaxHeap(a, len, targetIndex); } }
void heapSort(int a[], int len) { if (len <= 1) { return; }
// 初始堆成无序最大堆 initHeap(a, len);
for (int i = len - 1; i > 0; --i) { // 将当前堆顶元素与最后一个元素交换，保证这一趟所查找到的堆顶元素与最后一个元素交换 // 注意：这里所说的最后不是a[len - 1]，而是每一趟的范围中最后一个元素 // 为什么要加上>0判断？每次不是说堆顶一定是最大值吗？没错，每一趟调整后，堆顶是最大值的 // 但是，由于len的范围不断地缩小，导致某些特殊的序列出现异常 // 比如说，5, 3, 8, 6, 4序列，当调整i=1时，已经调整为3,4,5,6,8序列，已经有序了 // 但是导致了a[i]与a[0]交换，由于变成了4,3,5,6,8反而变成无序了! if (a[0] > a[i]) { int temp = a[0]; a[0] = a[i]; a[i] = temp; }
// 范围变成为： // 0...len-1 // 0...len-1-1 // 0...1 // 结束 // 其中，0是堆顶，每次都是找出在指定的范围内比堆顶还大的元素，然后与堆顶元素交换 adjustMaxHeap(a, i - 1, 0); } }
|
基于最小堆实现降序排序
|
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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
// 初始化堆 void initHeap(int a[], int len) { // 从完全二叉树最后一个非子节点开始 // 在数组中第一个元素的索引是0 // 第n个元素的左孩子为2n+1，右孩子为2n+2， // 最后一个非子节点位置在(n - 1) / 2 for (int i = (len - 1) / 2; i >= 0; --i) { adjustMinHeap(a, len, i); } }
void adjustMinHeap(int a[], int len, int parentNodeIndex) { // 若只有一个元素，那么只能是堆顶元素，也没有必要再排序了 if (len <= 1) { return; }
// 记录比父节点大的左孩子或者右孩子的索引 int targetIndex = -1;
// 获取左、右孩子的索引 int leftChildIndex = 2 * parentNodeIndex + 1; int rightChildIndex = 2 * parentNodeIndex + 2;
// 没有左孩子 if (leftChildIndex >= len) { return; }
// 有左孩子，但是没有右孩子 if (rightChildIndex >= len) { targetIndex = leftChildIndex; } // 有左孩子和右孩子 else { // 取左、右孩子两者中最上的一个 targetIndex = a[leftChildIndex] < a[rightChildIndex] ? leftChildIndex : rightChildIndex; }
// 只有孩子比父节点的值还要小，才需要交换 if (a[targetIndex] < a[parentNodeIndex]) { int temp = a[targetIndex];
a[targetIndex] = a[parentNodeIndex]; a[parentNodeIndex] = temp;
// 交换完成后，有可能会导致a[targetIndex]结点所形成的子树不满足堆的条件， // 若不满足堆的条件，则调整之使之也成为堆 adjustMinHeap(a, len, targetIndex); } }
void heapSort(int a[], int len) { if (len <= 1) { return; }
// 初始堆成无序最小堆 initHeap(a, len);
for (int i = len - 1; i > 0; --i) { // 将当前堆顶元素与最后一个元素交换，保证这一趟所查找到的堆顶元素与最后一个元素交换 // 注意：这里所说的最后不是a[len - 1]，而是每一趟的范围中最后一个元素 // 为什么要加上>0判断？每次不是说堆顶一定是最小值吗？没错，每一趟调整后，堆顶是最小值的 // 但是，由于len的范围不断地缩小，导致某些特殊的序列出现异常 // 比如说，5, 3, 8, 6, 4序列，当调整i=1时，已经调整为3,4,5,6,8序列，已经有序了 // 但是导致了a[i]与a[0]交换，由于变成了4,3,5,6,8反而变成无序了! if (a[0] < a[i]) { int temp = a[0]; a[0] = a[i]; a[i] = temp; }
// 范围变成为： // 0...len-1 // 0...len-1-1 // 0...1 // 结束 // 其中，0是堆顶，每次都是找出在指定的范围内比堆顶还小的元素，然后与堆顶元素交换 adjustMinHeap(a, i - 1, 0); } }
|
C语言版测试
大家可以测试一下：
|
1 2 3 4 5 6 7 8 9 |
// int a[] = {5, 3, 8, 6, 4}; int a[] = {89,-7,999,-89,7,0,-888,7,-7}; heapSort(a, sizeof(a) / sizeof(int));
for (int i = 0; i < sizeof(a) / sizeof(int); ++i) { NSLog(@"%d", a[i]); }
|
Swift版实现
基于最大堆实现升序排序
|
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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
func initHeap(inout a: [Int]) { for var i = (a.count - 1) / 2; i >= 0; --i { adjustMaxHeap(&a, len: a.count, parentNodeIndex: i) } }
func adjustMaxHeap(inout a: [Int], len: Int, parentNodeIndex: Int) { // 如果len <= 0，说明已经无序区已经缩小到0 guard len > 1 else { return }
// 父结点的左、右孩子的索引 let leftChildIndex = 2 * parentNodeIndex + 1
// 如果连左孩子都没有， 一定没有右孩子，说明已经不用再往下了 guard leftChildIndex < len else { return }
let rightChildIndex = 2 * parentNodeIndex + 2
// 用于记录需要与父结点交换的孩子的索引 var targetIndex = -1
// 若没有右孩子，但有左孩子，只能选择左孩子 if rightChildIndex > len { targetIndex = leftChildIndex } else { // 左、右孩子都有，则需要找出最大的一个 targetIndex = a[leftChildIndex] > a[rightChildIndex] ? leftChildIndex : rightChildIndex }
// 只有孩子比父结点还要大，再需要交换 if a[targetIndex] > a[parentNodeIndex] { let temp = a[targetIndex]
a[targetIndex] = a[parentNodeIndex] a[parentNodeIndex] = temp
// 由于交换后，可能会破坏掉新的子树堆的性质，因此需要调整以a[targetIndex]为父结点的子树，使之满足堆的性质 adjustMaxHeap(&a, len: len, parentNodeIndex: targetIndex) } }
func maxHeapSort(inout a: [Int]) { guard a.count > 1 else { return }
initHeap(&a)
for var i = a.count - 1; i > 0; --i { // 每一趟都将堆顶交换到指定范围内的最后一个位置 if a[0] > a[i] { let temp = a[0]
a[0] = a[i] a[i] = temp } print(a) print(i - 1) // 有序区长度+1，而无序区长度-1，继续缩小无序区，所以i-1 // 堆顶永远是在0号位置，所以父结点调整从堆顶开始就可以了 adjustMaxHeap(&a, len: i - 1, parentNodeIndex: 0) print(a) } }
|
基于最小堆降序排序
|
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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
func initHeap(inout a: [Int]) { for var i = (a.count - 1) / 2; i >= 0; --i { adjustMinHeap(&a, len: a.count, parentNodeIndex: i) } }
func adjustMinHeap(inout a: [Int], len: Int, parentNodeIndex: Int) { // 如果len <= 0，说明已经无序区已经缩小到0 guard len > 1 else { return }
// 父结点的左、右孩子的索引 let leftChildIndex = 2 * parentNodeIndex + 1
// 如果连左孩子都没有， 一定没有右孩子，说明已经不用再往下了 guard leftChildIndex < len else { return }
let rightChildIndex = 2 * parentNodeIndex + 2
// 用于记录需要与父结点交换的孩子的索引 var targetIndex = -1
// 若没有右孩子，但有左孩子，只能选择左孩子 if rightChildIndex > len { targetIndex = leftChildIndex } else { // 左、右孩子都有，则需要找出最大的一个 targetIndex = a[leftChildIndex] < a[rightChildIndex] ? leftChildIndex : rightChildIndex }
// 只有孩子比父结点还要大，再需要交换 if a[targetIndex] < a[parentNodeIndex] { let temp = a[targetIndex]
a[targetIndex] = a[parentNodeIndex] a[parentNodeIndex] = temp
// 由于交换后，可能会破坏掉新的子树堆的性质，因此需要调整以a[targetIndex]为父结点的子树，使之满足堆的性质 adjustMinHeap(&a, len: len, parentNodeIndex: targetIndex) } }
func minHeapSort(inout a: [Int]) { guard a.count > 1 else { return }
initHeap(&a)
for var i = a.count - 1; i > 0; --i { // 每一趟都将堆顶交换到指定范围内的最后一个位置 if a[0] < a[i] { let temp = a[0]
a[0] = a[i] a[i] = temp } else { return // 可以直接退出了，因为已经全部有序了 }
// 有序区长度+1，而无序区长度-1，继续缩小无序区，所以i-1 // 堆顶永远是在0号位置，所以父结点调整从堆顶开始就可以了 adjustMinHeap(&a, len: i - 1, parentNodeIndex: 0) } }
|
测试：
|
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 |
var arr = [5, 3, 8, 6, 4] //var arr = [89,-7,999,-89,7,0,-888,7,-7] maxHeapSort(&arr)
print(arr)
// 打印日志如下： [4, 6, 5, 3, 8] 3 [6, 4, 5, 3, 8]
[3, 4, 5, 6, 8] 2 [5, 4, 3, 6, 8]
[3, 4, 5, 6, 8] 1 [3, 4, 5, 6, 8]
[3, 4, 5, 6, 8] 0 [3, 4, 5, 6, 8]
[3, 4, 5, 6, 8]
|
最后
花了将近一天半的时间来整理这篇文章，同时深入地理解这个算法。这个过程中，查了很多篇博客讲解堆排序的，但是都是很难去理解，而且所提供的代码都是有一定问题的。经过这么一折腾，终于把堆排序给理明白了。如果大家在学习时遇到问题，再联系笔者吧！