堆排序及堆的应用

不同于直接对序列中的数据进行排序的归并排序和快排，堆排序是一种利用数据结构的特性来辅助排序的算法，排序的过程可以分为建堆和减堆两个阶段。除了排序功能外，堆这个结构对于解决一些实时的流数据的调整问题是极为高效的，在操作系统中，处理进程的优先级队列就是堆的一种应用方式。本文重点介绍一下堆排序的算法思想，实现以及堆这种结构在算法中的应用。

堆结构

学习堆排序之前我们必须要对堆这种结构有一个清楚地认识，而要认识堆这个结构，我们先要铺垫一些关于二叉树的概念。

完全二叉树

我们都知道，树是一种双分支的层次结构，从根结点开始，每一个结点最多可以有左右两个分支，也可以没有分支，我们将没有子结点的结点称为叶子结点，而一棵二叉树的层数我们也称为深度。下面来理清两个概念：

满二叉树：对于一棵二叉树，每一层都满足第i层的结点个数为2^i-1个时，这棵二叉树为满二叉树；直观来看整个二叉树呈三角形，且每一个结点都是补全的，如图所示：

完全二叉树：对于一棵二叉树，其深度为i，如果前i-1层满足满二叉树的定义，且第i层的结点排列顺序是由左往右依次补全，这棵二叉树为完全二叉树；直观来看是在满二叉树的基础上由右往左，由下往上的缺失结点（或者说由左往右，由上往下的增添结点），如图所示：

堆

实质上，堆的逻辑结构就是一颗完全二叉树，只不过完全二叉树只关心整棵树的逻辑结构，不关心结点之间的顺序，而堆这个结构要求的是各个结点所代表的值必须呈现出一定的规律性。具体来说可以分为大根堆和小根堆两种结构，大根堆要求树中每一个结点的值都要小于自己的父结点（如果存在），大于自己的左右子结点（如果存在）；类似的小根堆则要求树中每一个结点的值都要大于自己的父结点（如果存在），小于自己的左右子结点（如果存在），如图所示：

注意，这里我们为什么要强调逻辑结构，之前在讲解对数器的时候我们说四种基本数据类型（集合，线性表，树和图）都属于逻辑结构，即拓扑意义上的表达，这样的结构便于我们对其进行研究和理解，而在实现层面上，我们可以任意地选择线性结构和链式结构来对其实现。具体到堆这个结构，顺序结构的实现我们一般采用数组，链式结构的实现则会才采用二叉树的结点实现方式，虽然理论上这两种结构都可以实现堆，但是堆的特性要求使得我们在建堆的过程中要不断对新加入的结点进行位置调整，以保证堆结构的顺序性，因此采用顺序结构的实现，我们可以很容易的实现结点之间的检索和交换，同时排序算法中给定序列也一般用顺序结构存储，故采用顺序结构可以在排序时之间进行建堆的操作。

堆排序

通过上文中对堆排序的介绍，我们了解到堆这个结构天生就有一定的顺序关系，利用这个特性，当我们将某个序列中的所有元素建成一个堆后，可以直接获取到序列中的最大值或最小值；此时将这个值拿掉之后，剩余的元素重新建堆，则获取到原序列中的次最大值或次最小值……以此类推，直到堆中的元素全部耗尽，我们也就得到了一个有序的序列。

建堆过程

上面只是将堆排序的思路从逻辑结构的角度大致描述了一下，但是涉及到具体数据结构的算法，因为代码的实现需要利用物理结构相应的优势和特性，逻辑层面的设想和物理层面的实现之间还要进行一系列相应的转换。具体到堆排序这个过程中，我们首先要考虑如何用顺序结构来模拟一个堆和堆的各种操作。

数组模拟堆：由于完全二叉树的结构特点，我们可以采用层序遍历的顺序对结点进行编号，同时对应数组的下标位置，如图所示：

在介绍堆结构时我们提到过，用顺序结构来实现堆可以很容易的实现结点之间的检索，这里我们就可以体会到，对于任意一个结点来说，他的父结点和左右孩子结点都可以通过简单地数组下标变换得到，总结后的规律如下：

若堆中结点x在数组中存放于i位置，如果存在父结点或左右孩子结点（数组中的判定条件为下标不越界），则有：

其父结点的数组下标：(i - 1) / 2

其左孩子的数组下标：2 * i + 1

其右孩子的数组下标：2 * i + 2

模拟建堆过程

堆的建立过程是一个逐步插入新元素同时逐步调整堆结构的过程，初始时堆内为空，每插入一个元素，就要对堆的整体结构进行调整。一般新插入的元素位于堆的最后一个位置（依完全二叉树的层序遍历顺序），调整的过程是该元素和父结点不断交换，逐渐上浮合理的位置，保证堆的“有序”。我们以大根堆为例，建堆的过程如图所示：

图中展示了序列【15,3,10,7,5,16,11,12】这个序列建堆的过程，绿色元素表示需要新插入堆中的元素，橙色双箭头的线代表元素之间存在交换关系，蓝色元素表示新插入的元素在调整堆结构后确定的位置。下面我们通过物理结构再来模拟一遍这个过程，如图所示：

与上一张图所表示的含义相同，绿色部分为新插入堆中的元素，蓝色部分为堆结构调整后的元素，不同的是这张图用实线和虚线区别开了元素比较和交换的过程，虚线表示元素之间的比较，实现表示元素之间的交换。我们看到基本上每插入一个新的元素，都要与其父结点的元素进行比较（根结点除外），根据的是上文中我们总结到的顺序结构下堆中具有父子关系的元素下标之间的规律，通过简单地下标变换我们就能知道新插入的元素是否需要上移；而只有当元素需要上移时，才进行父子结点的元素交换，依然可以通过下表变换实现。

注意，图中由于区域有限，将比较和交换的过程进行了统一的标注，并非表示比较和交换是分割的两个阶段，在实际的代码逻辑中比较和交换是交替进行的，一次比较之后进行一次交换，之后再次比较，直到交换到合适的位置。

下面我们来构建建堆的代码，这里仍旧以大根堆为例：

/**
 * 建立大根堆，将新加入的结点逐步向上调整，形成大根堆
 * @param arr
 * @param index
 */
public static void heapInsert(int[] arr,int index) {
	// 兼顾根结点和自身的比较
	while (arr[index] > arr[(index - 1) / 2]) {
		swap(arr, index, (index - 1) / 2);
		index = (index - 1) / 2;
	}
}

我们看到，建立大根堆的代码非常简洁，通过外部循环传入要插入的新元素的数组下标，与现有的大根堆进行调整合并，由于比较和交换的逻辑是一旦子结点的元素值大于父结点就需要交换，否则说明当前位置就是新插入的元素合理的位置。heapInsert直接通过一个while循环，同时兼顾了这两方面的逻辑，如果新插入的元素值大于父结点的元素，则两个结点交换，新元素再次和新的父结点作比较，一旦到新元素的值小于父结点，该方法直接返回。

有同学可能会担心数组的下标是否有可能越界，其实是不会的，因为代码逻辑对数组的下标只会减小不会增大，所以当新元素交换到根结点时，他会经历一次自己和自己比较的过程，由于自己不会大于自己所以也会循环结束跳出方法。

减堆过程

现在整个包含所有元素的大根堆已经建好，堆顶元素即为该序列的最大值，我们下一步的任务就是把最大值从堆中排除出去，重新调整堆找出次最大值，逐渐把这个堆减小，最终获得整个有序序列。这个过程我们首先要考虑的问题是，这个排除出堆的最大值，我们应该如何处理，如何保存，是否需要额外的辅助空间？其实是不用的，这就又要说道顺序结构来实现堆这一逻辑结构的优势，正如我们在建堆的过程中，也并没有申请额外的辅助空间来保存这个新建好的堆，因为序列中的元素是一定的，不论是在建堆还是减堆的过程中，任何一个序列中的元素要么在堆中，要么在堆外（可以认为在原数组中），即我们可以将整个数组看做堆部分与非堆部分，只要这两个部分相互隔离（用指针区分），就不用申请多的辅助空间，因此我们可以将建好的堆的最大元素与堆中末尾的元素交换位置，同时将堆的大小减一，就可以解决这个问题。

至于为什么一定要选择最后一个位置来做交换呢，两个原因。第一，正如上面所说的，我们需要让堆部分和非堆部分分隔开，那么只有把元素往两边放，不能跨元素产生交叉；那为什么不直接将最大值留在原地，堆的范围向后缩减呢？这就是第二个原因导致的，我们在建堆的过程中已经形成的大根堆通过元素的下标变化可以得到他的父子结点，而他们之间的次序关系已经是调整好了的，如果我们这时去掉队尾的元素，其实对整个堆的结构不会产生任何影响，反而一旦我们损失了堆头的位置，整个堆的结构就无法再利用，需要重新排列（建堆），生成新的堆顶，这样会产生很多额外的时间成本，得不偿失。综上，我们选择堆尾元素作为与堆顶最大值交换的元素，这样队尾元素就成了新的堆顶元素。

如此一来虽然堆的大小减一，但是整个堆的结构性被破坏了，需要重新调整堆顶元素的位置，这也是减堆过程中最关键的步骤。不用于建堆过程中元素从下往上移动，减堆时队尾元素本来应该位于堆的最底层，下载要从堆顶位置向下移动和合适的位置。

还是通过上面举的例子，下面我们通过第一次换元素并重新调整堆的过程来看一下减堆时应当如何对堆进行调整，如图所示：

为了便于对比，我们直接将逻辑结构的减堆过程和物理结构的减堆过程画在同一张图中，我们看到，初始状态下整个堆结构有序，指针也指向数组的最后一个位置，当交换堆顶和堆尾元素后，指针前移，指针以后的数组部分“变黑”，表示之后的部分已经不在堆结构之中。接下来，交换到堆顶的元素开始和他的左右孩子结点的值两两比较，同时当该元素的值小于孩子结点的元素时与孩子结点中较大值交换，直到该元素的值大于任何一个孩子结点或者该元素下移至叶子结点（图中结点3的情况）。

下面我们配合代码再加深一步理解：

/**
 * 已形成的大根堆在某个结点发生变化后如何进行调整，调整结点逐步下沉
 * @param arr
 * @param current
 * @param index	要调整的堆的范围
 */
public static void heapify(int[] arr,int current,int index) {
	while((current *2 + 1)<index) {
		int leftChild = current *2 + 1;
		int rightChild = current *2 + 2;
		int large = rightChild<index&&arr[rightChild]>arr[leftChild]?rightChild:leftChild;
		large = arr[current]<arr[large]?large:current;
		//当前数比左右孩子都大，不用再进行交换
		if(current == large)
			break;
		swap(arr, current, large);
		current = large;
	}
}

我们发现，代码相比之前分析的逻辑更进一步进行了封装，使得该方法的适用范围更广，功能更强大。我们的减堆逻辑是将最后堆顶元素和堆尾元素进行交换，之后从堆顶开始重新调整堆结构，而这其中其实隐含着一个更普遍的功能需求，即在一个堆中，从某一个结点开始，其下的堆结构需要重新排序，也就是说这个结点不一定是根结点，也有可能是堆中的任何一个结点。current变量就是用来指明需要从哪个结点开始从上到下重新调整堆，index变量限制了堆的大小，将堆内元素和堆外元素做了分隔。

注意：代码中的index边界返回与我们图中的index所指向的位置有所出入，代码为了书写简洁将index的位置向后移动了一位，大家理解时要注意这一点。

下面我们来看一下代码的内部逻辑，与建堆过程中结点向上移动的逻辑不同，向下移动时涉及到结点选择的问题，毕竟二叉树结构中父结点只有一个，子结点可能有多个；并且，结点的向下移动意味着在迭代的过程中索引值会不断变大，我们要注意数组下标的越界问题。

整个函数的逻辑嵌套在一个循环中，循环的条件是新的堆顶元素在下移的过程中是否移动到了叶结点处，一点该元素移动到了叶子结点处，即该元素没有下移空间了，直接跳出循环；循环内部使用了两个三目表达式用于求出当前元素以及其左右孩子结点的值之间的最大值，同时兼顾了对下标越界的判断，将最大值的下标保存在large变量中。这时，判断large和current是否相等，即判断当前值是否就是三者中的最大值，如果是则不需要再下移，直接break跳出循环；否则，交换当前元素和large所指向的元素，current指针更新，进行下一次的迭代。

现在，学习完了堆排序的两个阶段，我们再来将建堆和减堆的堆调整函数放入整个堆排序的流程中，体会一下整个过程，代码如下：

public static void heapSort(int[] arr) {
	if(arr==null||arr.length<2)
		return;
	//建堆过程
	for (int i = 0; i < arr.length; i++) {
		heapInsert(arr, i);
	}
	//减堆过程
	int heapSize = arr.length;
	while(heapSize-->0) {
		swap(arr, 0, heapSize);
		heapify(arr, 0, heapSize);
	}
}

外部函数的代码逻辑基本上和逻辑层面的堆排序过程如出一辙，首先进行建堆，建堆的过程是逐个将数组中的元素插入到堆中，插入的同时进行堆结构调整（这一过程封装在heapInsert函数中）；建堆完成后开始减堆，随着堆范围一步步向内缩减，堆顶的元素被交换出堆外，再对新交换到堆顶的元素进行调整（这一过程封装在heapify函数中），直到堆内元素耗尽。

算法剖析

前面我们说到，堆排序虽然借助了额外的数据结构来辅助我们进行排序，但是这只是逻辑上的应用，物理结构上我们不论是建堆还是减堆的过程，自始至终使用的都是原始的给定数组，并没有申请额外的辅助空间，因此堆排序的空间复杂度是O(1)的。而时间复杂度我们可以将两个阶段分开来看，因为建堆和减堆的过程完全是串行执行的，因此总的时间复杂度应该是建堆时间加上减堆时间。

注意，除了上文中所介绍的自顶向下（maxHeapInsert）的建堆方式以外，其实还有一种自底向上（buildMaxHeap）的建堆方法，所谓的自底向上指的是我们在建堆之前已知所有要插入的元素及其顺序的情况下，先将其构建成一棵完全二叉树，接着按照层序遍历的逆序方式，从第一个非叶子结点开始，依次对每个结点执行一个heapify的过程，即对完全二叉树中的每一棵子树逐渐调整建堆，最终建出整个堆来，这个过程和自顶向下的建堆顺序正好相反，先处理下层节点的位置和下层子树的堆结构，逐渐向上形成最终整个堆结构的有序。

下面我们来比较一下这两种建堆方式的时间复杂度，看看这两种建堆方式在时间上谁更快一些。我们先来对整个堆上的基准数据做一假设和定义，假设整个堆是一棵满二叉树，叶子结点为第0层，由下往上依次递进，总结点个数为N，则有堆的深度为log₂N，建堆过程中结点的比较和交换只与其所在的层数有关，和整个堆的结点个数无关，因此同一层的结点所要比较和交换的次数相同，堆的层数，每一层的节点数以及两种建堆方式每一层需要比较和移动的次数的对应关系如下表所示：

层数	结点个数	自顶向下移动次数	自底向上移动次数
0	(N+1)/2	log₂N	0
1	(N+1)/4	log₂N-1	1
2	(N+1)/8	log₂N-2	2
……	……	……	……
k	N+1/2^k+1	log₂N-k	k
……	……	……	……
log₂N-1	(N+1)/2^log₂N	1	log₂N-1
log₂N	(N+1)/2^log₂N+1	0	log₂N

注意，以下我们所提到的结点之间的比较和交换只按单次计算，一般以第一次加入堆结构时的调整次数为准，之后因为其他结点的调整所产生的被动比较和交换不计入时间复杂度中。

自顶向下

自顶向下的建堆方式，结点的比较和交换是一个从下到上的过程，越靠下层的结点越晚加入到堆结构中，所需要进行移动的次数也更多。堆顶元素自然成堆，无须比较和交换，堆顶的下一层结点最多需要比较和交换一次，即可到达堆顶位置……以此类推，最后一次叶子结点需要比较和交换总的深度减一次。一次建堆过程总的比较次数累加表达式如下图所示：

推导结果中当N趋于无穷大时，常数项无意义，1/2N趋于0，最终结果化简为Nlog₂N，因此自顶向下的建堆方式时间复杂度为O(Nlog(N))。

自底向上

自底向上的建堆方式，结点的比较和交换是一个从上到下的过程，越靠下层的结点越早加入到堆结构中，所需要进行移动的次数也越少。叶子结点不需要进行下移直接有序，叶子结点的上一层结点最多需要比较和交换一次，即可到达堆底位置……以此类推，最后一次堆顶结点需要比较和交换总的深度减一次。一次建堆过程总的比较次数累加表达式如下图所示：

推导结果中当N趋于无穷大时，常数项无意义，1/2N趋于0，指数函数和一次函数的比值可用洛必达公式化简得结果任然趋于0（显然指数函数是比一次函数更高阶的无穷小），最终结果化简为N，因此自底向上的建堆方式时间复杂度为O(N)。

这篇博客对两种建堆的方式进行了更深入比较和数学证明，有兴趣的同学可以阅读一下。

虽然我们最终得出的结论是自底向上的建堆方式在时间性能上更优，但是前提是我们需要在建堆之前就得到所有的结点信息和减堆次序，对数据状况的要求更为苛刻，适用度不如自顶向下的方式更加通用，并且我们提到堆结构的优势正是在于处理实时的流数据，因此对于一般情况我们还是采取自顶向下的建堆方式，用一一点的时间成本获得更大的功能扩展。

至于建堆的时间复杂度，我们可以参考自底向上的建堆过程，因为这一过程使用的方式也是减堆过程中大量使用的heapify操作。与建堆过程不同的是，减堆时所执行的heapify操作都是对整个堆的堆顶元素执行的，而每一次操作堆顶元素都要执行整个堆的深度的比较和交换，因此时间复杂度为O(log(N))，直到堆中所有元素全部出堆，整个过程的时间复杂度为O(Nlog(N))。综上，不论建堆的时间复杂度如何，减堆的过程直接限制了堆排序的时间复杂度维持在O(Nlog(N))的层级上，无法再降低。

堆的应用

由于堆这个结构利用了完全二叉树这一数据分布非常平均的结构，因此任何时候对堆中的元素进行调整的代价只会和堆的深度有关，而不会和整个数量级相关，而O(log(N))的代价无疑是非常低的，对于一个四十多亿的数据量O(log(N))的代价也仅仅是32次。不仅如此，堆结构对整个序列中最值的检索操作是O(1)的，这就为我们设计许多实时处理信息检索的数据结构提供了便利，下面我们来看一个案例。

求中位数

题目：设计一个结构，实现将一个数据流中不断产生的整数保存起来，并且在任意时刻给出当前序列的中位数
要求：求中位数的时间复杂度为O(1)
分析：
- 对于一个有序序列，我们很容易通过中间位置的索引值得到中位数，时间复杂度为O(1)，但是面对一个无序的序列，我们想用通过次序关系获取中位数，就不得不先承担一个排序的时间复杂度，而我们已知的排序算法中，最短也需要O(Nlog(N))的时间，但是本题处理的是一个流式数据，就是说我们如果要通过以上方式获取中位数，那么只需要从最开始建立序列的时候保持每次获得数时序列的有序性，即我们每获得一个数就通过插入的方式将新获得的数插入到原有序列的适当位置，继续保持序列的有序性，这样只需要花费O(N)的时间复杂度，我们就可以任何时刻以O(1)的时间获取整个序列中位数。
- 但是我们考虑对于题目求中位数的要求，我们只需要知道整个序列较大的一半数（以及其中的最小值）和较小的一半数（以及其中的最大值）即可，两个部分其中的次序关系对于求整个序列的中位数其实没有帮助，但是为了得到有序序列我们还是付出了额外的时间复杂度。有没有方式能够保存一个流式数据的最值呢，很自然的我们想到堆结构，利用堆结构对处理流数据的低时间成本我们还能有效降低保持局部有序性的时间复杂度。
思路：正如上面的分析，我们可以创建两个堆，分别保存流序列中较大的一半值和较小的一半值，储存较大值的为小根堆，储存较小值的为大根堆，这样就能分别保存位于中间位置的两个值，在获取数的时候我们通过一定的逻辑选择数进哪个堆，而当堆之间出现失衡时（元素数量差大于1），两个堆之间出堆入堆在调整堆结构，这些操作都可以在O(log(N))的时间内完成。

详细的控制逻辑我们用程序的流程图来表示：