1、28|堆和堆排序：为什么说堆排序没有快速排序快？ file:/F/temp/geektime/数据结构与算法之美/28堆和堆排序：为什么说堆排序没有快速排序快？.html2019/1/15 15:36:02 28|堆和堆排序：为什么说堆排序没有快速排序快？ 我们今天讲另外一种特殊的树，“堆”（$Heap$）。堆这种数据结构的应用场景非常多，最经典的莫过于堆排序了。堆排序是一种原地的、时间复杂度为$O(nlog n)$的排序算法。 前面我们学过快速排序，平均情况下，它的时间复杂度为$O(nlog n)$。尽管这两种排序算法的时间复杂度都是$O(nlog n)$，甚至堆排序比快速排序的时间复杂度
2、还要稳定，但是，在实际的软件开发中，快速排序的性能要比堆排序好，这是为什么呢？ 现在，你可能还无法回答，甚至对问题本身还有点疑惑。没关系，带着这个问题，我们来学习今天的内容。等你学完之后，或许就能回答出来了。 如何理解“堆”？ 前面我们提到，堆是一种特殊的树。我们现在就来看看，什么样的树才是堆。我罗列了两点要求，只要满足这两点，它就是一个堆。 堆是一个完全二叉树； 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。 我分别解释一下这两点。 第一点，堆必须是一个完全二叉树。还记得我们之前讲的完全二叉树的定义吗？完全二叉树要求，除了最后一层，其他层的节点个数都是满的，最后一层的节
3、点 都靠左排列。 第二点，堆中的每个节点的值必须大于等于（或者小于等于）其子树中每个节点的值。实际上，我们还可以换一种说法，堆中每个节点的值都大于等于（或者小 于等于）其左右子节点的值。这两种表述是等价的。 对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫作“小顶堆”。 定义解释清楚了，你来看看，下面这几个二叉树是不是堆？ 28|堆和堆排序：为什么说堆排序没有快速排序快？ file:/F/temp/geektime/数据结构与算法之美/28堆和堆排序：为什么说堆排序没有快速排序快？.html2019/1/15 15:36
4、:02 其中第$1$个和第$2$个是大顶堆，第$3$个是小顶堆，第$4$个不是堆。除此之外，从图中还可以看出来，对于同一组数据，我们可以构建多种不同形态的堆。 28|堆和堆排序：为什么说堆排序没有快速排序快？ file:/F/temp/geektime/数据结构与算法之美/28堆和堆排序：为什么说堆排序没有快速排序快？.html2019/1/15 15:36:02 如何实现一个堆？ 要实现一个堆，我们先要知道，堆都支持哪些操作以及如何存储一个堆。 我之前讲过，完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针，单纯地通过数组的 下标，
5、就可以找到一个节点的左右子节点和父节点。 我画了一个用数组存储堆的例子，你可以先看下。 从图中我们可以看到，数组中下标为$i$的节点的左子节点，就是下标为$i*2$的节点，右子节点就是下标为$i*2+1$的节点，父节点就是下标为$fraci2$的节 点。 知道了如何存储一个堆，那我们再来看看，堆上的操作有哪些呢？我罗列了几个非常核心的操作，分别是往堆中插入一个元素和删除堆顶元素。（如果没有特殊 28|堆和堆排序：为什么说堆排序没有快速排序快？ file:/F/temp/geektime/数据结构与算法之美/28堆和堆排序：为什么说堆排序没有快速排序快？.html2019/1/15 15:36:
6、02 说明，我下面都是拿大顶堆来讲解）。 1.往堆中插入一个元素 往堆中插入一个元素后，我们需要继续满足堆的两个特性。 如果我们把新插入的元素放到堆的最后，你可以看我画的这个图，是不是不符合堆的特性了？于是，我们就需要进行调整，让其重新满足堆的特性，这个过程我 们起了一个名字，就叫作堆化（heapify）。 堆化实际上有两种，从下往上和从上往下。这里我先讲从下往上的堆化方法。 28|堆和堆排序：为什么说堆排序没有快速排序快？ file:/F/temp/geektime/数据结构与算法之美/28堆和堆排序：为什么说堆排序没有快速排序快？.html2019/1/15 15:36:02 堆化非常简单
7、，就是顺着节点所在的路径，向上或者向下，对比，然后交换。 我这里画了一张堆化的过程分解图。我们可以让新插入的节点与父节点对比大小。如果不满足子节点小于等于父节点的大小关系，我们就互换两个节点。一直重 复这个过程，直到父子节点之间满足刚说的那种大小关系。 28|堆和堆排序：为什么说堆排序没有快速排序快？ file:/F/temp/geektime/数据结构与算法之美/28堆和堆排序：为什么说堆排序没有快速排序快？.html2019/1/15 15:36:02 我将上面讲的往堆中插入数据的过程，翻译成了代码，你可以结合着一块看。 28|堆和堆排序：为什么说堆排序没有快速排序快？ file:/F/t
8、emp/geektime/数据结构与算法之美/28堆和堆排序：为什么说堆排序没有快速排序快？.html2019/1/15 15:36:02 public class Heap private int a; / 数组，从下标1开始存储数据 private int n; / 堆可以存储的最大数据个数 private int count; / 堆中已经存储的数据个数 public Heap(int capacity) a = new intcapacity + 1; n = capacity; count = 0; public void insert(int data) if (count = n
9、) return; / 堆满了 +count; acount = data; int i = count; while (i/2 0 / swap()函数作用：交换下标为i和i/2的两个元素 i = i/2; 2.删除堆顶元素 从堆的定义的第二条中，任何节点的值都大于等于（或小于等于）子树节点的值，我们可以发现，堆顶元素存储的就是堆中数据的最大值或者最小值。 假设我们构造的是大顶堆，堆顶元素就是最大的元素。当我们删除堆顶元素之后，就需要把第二大的元素放到堆顶，那第二大元素肯定会出现在左右子节点中。 然后我们再迭代地删除第二大节点，以此类推，直到叶子节点被删除。 这里我也画了一个分解图。不过这种
10、方法有点问题，就是最后堆化出来的堆并不满足完全二叉树的特性。 28|堆和堆排序：为什么说堆排序没有快速排序快？ file:/F/temp/geektime/数据结构与算法之美/28堆和堆排序：为什么说堆排序没有快速排序快？.html2019/1/15 15:36:02 实际上，我们稍微改变一下思路，就可以解决这个问题。你看我画的下面这幅图。我们把最后一个节点放到堆顶，然后利用同样的父子节点对比方法。对于不满 足父子节点大小关系的，互换两个节点，并且重复进行这个过程，直到父子节点之间满足大小关系为止。这就是从上往下的堆化方法。 因为我们移除的是数组中的最后一个元素，而在堆化的过程中，都是交换操作
11、，不会出现数组中的“空洞”，所以这种方法堆化之后的结果，肯定满足完全二叉树 的特性。 28|堆和堆排序：为什么说堆排序没有快速排序快？ file:/F/temp/geektime/数据结构与算法之美/28堆和堆排序：为什么说堆排序没有快速排序快？.html2019/1/15 15:36:02 我把上面的删除过程同样也翻译成了代码，贴在这里，你可以结合着看。 public void removeMax() if (count = 0) return -1; / 堆中没有数据 a1 = acount; -count; heapify(a, count, 1); 28|堆和堆排序：为什么说堆排序没有
12、快速排序快？ file:/F/temp/geektime/数据结构与算法之美/28堆和堆排序：为什么说堆排序没有快速排序快？.html2019/1/15 15:36:02 private void heapify(int a, int n, int i) / 自上往下堆化 while (true) int maxPos = i; if (i*2 = n if (i*2+1 = n -i) heapify(a, n, i); private static void heapify(int a, int n, int i) while (true) int maxPos = i; if (i*2
13、= n if (i*2+1 = n -k; heapify(a, k, 1); 现在，我们再来分析一下堆排序的时间复杂度、空间复杂度以及稳定性。 整个堆排序的过程，都只需要极个别临时存储空间，所以堆排序是原地排序算法。堆排序包括建堆和排序两个操作，建堆过程的时间复杂度是$O(n)$，排序过程 的时间复杂度是$O(nlog n)$，所以，堆排序整体的时间复杂度是$O(nlog n)$。 堆排序不是稳定的排序算法，因为在排序的过程，存在将堆的最后一个节点跟堆顶节点互换的操作，所以就有可能改变值相同数据的原始相对顺序。 今天的内容到此就讲完了。我这里要稍微解释一下，在前面的讲解以及代码中，我都假设，堆中的数据是从数
