排序算法：Heap Sort 堆排序与 Top K 问题
The following article is from ProjectDaedalus Author 程序员 Aaron Zhu
（给算法爱好者加星标，修炼编程内功）
来源：程序员 Aaron Zhu（本文来自作者投稿）
现代基础性计算环境中，输入量的元素规模N会非常大，但有时候会只要求从中找出K个最大(或最小)的元素，即Top K问题。如果使用之前介绍的传统排序算法，先对N个元素进行全排序然后再取前K个元素，计算代价会变的非常高昂。因为我们实际上只需要Top K元素的排序，而剩余元素的详细排序结果我们其实并不care。而本文介绍的Heap Sort堆排序不仅是一种高效的排序算法，还可以很好地解决Top K问题
二叉堆
定义
堆 Heap, 一种特殊的树状数据结构。在堆中，对于任意节点都有其值恒大于等于或小于等于其子节点的值，前者称之为max heap最大堆，后者则称之为min heap最小堆。常见的堆有:二叉堆、多叉堆、斐波那契堆等。这里我们所使用的即是二叉堆，其在形式上是一个完全二叉树
一般地，我们通过数组来实现二叉堆，将堆中元素按从上到下、从左到右的层级顺序依次存储到数组中即可(一般地为简便起见，通常从数组的第二个位置开始存储元素，不使用数组索引为0的位置。故大小为N的堆，所需数组的空间大小为N+1)。下图即为一个最大堆的存储示意图(为简便起见，下文中的"堆"均特指"二叉堆")
在一个堆中，对于位置为k节点，根据上图可知，其父节点在数组中的位置索引为 floor(k/2)，其两个子节点在数组中的位置索引分别为2*k、2*k+1
堆有序化
一个堆可能会由于某种原因打破其本来的有序状态，此时就需要重新调整来恢复、保证堆的有序状态，这个调整恢复的过程就称之为堆的有序化
堆有序:当一颗二叉树的任意节点恒大于等于或小于等于其两个子节点时，即被称为堆有序
本文我们以最大堆为例进行介绍，最小堆与其大同小异，此处将不再赘述。具体地，当一个堆的根节点元素被较小的元素替换时，我们就需要自上而下地恢复堆的有序化；当向堆底插入一个新节点时，我们则需要自下而上地恢复堆的有序化
1. 自上而下的堆有序化(下沉)
当一个最大堆的有序状态因为某个节点比其(两个或其中一个)子节点更小而被打破时，那么可以通过将该节点与其两个子节点中的较大者交换来恢复堆，该过程形象化地被称为"下沉"。交换后，可能会导致其在子节点处依然会继续打破堆的有序化，故我们需要不断地使用相同的方式将其进行修复，将节点向下移动直到其子节点均比其更小或到达了堆的底部。下图即是一个值为3的节点通过"下沉"恢复堆的有序化的过程
2. 自下而上的堆有序化(上浮)
当一个最大堆的有序状态因为某个节点比其父节点更大而被打破时，那么可以通过将该节点与其父节点交换来恢复堆，该过程形象化地被称为"上浮"。交换后，可能会导致其在父节点处依然会继续打破堆的有序化，故我们需要不断地使用相同的方式将其进行修复，将节点向上移动直到其父节点节点比其更大或成为了堆的根节点。下图即是一个值为25的节点通过"上浮"恢复堆的有序化的过程
Java 实现
Java的ArrayList是一个自动扩容的动态数组列表，故可用其实现最大堆。实现代码如下所示
/*** 堆排序*/public class HeapSort {/*** 最大堆*/private static ArrayList<Integer> maxHeap;/*** 获取堆的大小* @return* @apiNote 大小为N的堆，其数组大小为N+1*/private static int getSize() {return maxHeap.size()-1;}/*** 上浮, 自下而上的堆有序化*/private static void swim(int k) {// 第 k 个元素不是根节点 且 比父节点大while ( k>1 && oneLTtwo(k/2,k) ) {swap(k, k/2); // 交换当前节点与父节点位置, 将当前节点上浮一层k = k/2;}}/*** 下沉, 自上而下的堆有序化* @param k* @param N 堆的大小*/private static void sink(int k, int N) {while( 2*k <= N ) { // 该节点存在(左)子节点int childIndex = 2 * k; // 该节点下较大子节点的索引// 该节点存在右子节点 且 左子节点小于右子节点if( childIndex<N && oneLTtwo(childIndex, childIndex+1) ) {childIndex++;}// 当前节点 不小于 子节点，则停止下沉if(! oneLTtwo(k, childIndex)) {break;}swap(k, childIndex); // 交换当前节点与较大子节点位置, 将当前节点下沉一层k = childIndex;}}/*** 交换两个元素* @param indexA* @param indexB*/private static void swap(int indexA, int indexB) {int elementA = maxHeap.get(indexA);int elementB = maxHeap.get(indexB);maxHeap.set(indexA, elementB);maxHeap.set(indexB, elementA);}/*** 第一个元素 是否小于 第二个元素* @param indexA* @param indexB* @return*/private static Boolean oneLTtwo(int indexA, int indexB) {if( maxHeap.get(indexA) < maxHeap.get(indexB) ) {return true;}return false;}}
Heap Sort 堆排序
算法思想
通过上文，我们知道构造一个大小为N的最大堆，我们就可通过根节点获取N个元素中最大的元素。这里我们以对N个元素进行升序排列为例，讲解堆排序的算法思想：
将N个元素构造成一个最大堆，其中array[0]位置不使用
从一个大小为N的最大堆中将根节点(N个元素中最大的元素)array[1]从堆中移出，放入数组最后的位置中，则array[N]元素排序完成
对剩下的大小为N-1的最大堆，重新进行堆的有序化: 将堆底元素array[N-1]放入根节点的位置array[1]，并通过"下沉"重现建立新堆的有序化
重复上述Step 2-3，直到最大堆中只剩一个元素时为止。此时N个元素即排序完成
从上可以看出，堆排序实际上也是选择排序的一种，其通过堆的特性每次选取最大(或最小)的元素完成排序
Java实现
通过上文我们知道，在进行堆排序前，我们首先要用N个元素建立一个最大堆。一般地做法是，对待排序数组按从左到右的顺序进行遍历，依次从堆底添加新元素，通过"上浮"的方式来完成一个大小为N的堆的建立。然而更高效的做法是，我们从堆的最后一个父节点开始从右往左、从下而上，依次通过"下沉"父节点的方式完成堆的构建。因为当一个父节点的两个子堆都是有序时，此时在该父节点上调用"下沉"方法，即可将它们变成一个堆。前者需要N次"上浮"才能将元素一个一个地添加到堆中以此来完成堆的构建；而后者则只需floor(N/2)次"下沉"即可将堆构建完成，因为一个大小为N的完全二叉树，叶子节点的数量至少为N/2个
/*** 堆排序*/public class HeapSort {/*** 最大堆*/private static ArrayList<Integer> maxHeap;/*** 升序排列*/public static void sort() {// 获取测试用例Integer[] array = getTestCase();maxHeap = new ArrayList<>();maxHeap.add(null); // 在索引为0上添加空元素, array[0]位置不使用maxHeap.addAll( Arrays.asList(array) );System.out.println("before sort: " + Arrays.toString(array) );// 通过下沉的方式构造最大堆int N = getSize(); // 最大堆大小for(int i=N/2; i>0; i--) {sink(i, N);}// 堆排序, 升序排列while (N>1) {swap(1, N); // 将当前堆的最大元素(根节点)从堆中移除, 放入正确的排序位置N--; // 更新当前最大堆的大小sink(1, N); // 对于剩余堆进行有序化}// 移除索引为0上的空元素maxHeap.remove(0);System.out.println("after sort: " + maxHeap );}/*** 获取堆的大小* @return* @apiNote 大小为N的堆，其数组大小为N+1*/private static int getSize() {return maxHeap.size()-1;}/*** 获取测试用例*/private static Integer[] getTestCase() {Integer[] caseArray = {3,7,10,1,4,9,8,5,2,6};return caseArray;}}
测试结果如下:
特性
Top K 问题
定义
Top K 问题：从N个元素中找出最大(或最小)的K个元素
解决方案
容易想到的是解决方案是，对N个元素进行排序，然后根据排序结果从中取出最大(或最小)的K个元素，但是当N的规模非常之大时，效率会非常低。而堆则可以很好解决地该问题。这里，我们以取出最小的K个元素为例，说明如何通过最大堆解决该问题(若是找出最大的K个元素，则应通过最小堆解决):
建立一个最大堆，遍历N个元素并重复下述 Step 2-3
若堆的大小未达到K时，直接将新元素放入堆底，然后通过"上浮"恢复堆的有序化
若堆的大小已经为K时，则比较根节点元素(即堆中最大元素)是否比新元素大。若是，则直接用新元素来替换该堆的根节点，并通过"下沉"恢复堆的有序化；若不是，则直接丢弃该新元素即可
当N个元素全部遍历完成后，此时堆中元素即为所要找出最小的K个元素
Java 实现
这里利用Java实现一个从N个元素找出最小的K个元素的Demo
/*** 堆排序*/public class HeapSort {/*** 最大堆*/private static ArrayList<Integer> maxHeap;/*** (Top K 问题) 取K个最小的元素*/public static void TopK() {Integer[] array = getTestCase();System.out.println("Input Array: " + Arrays.toString(array) );int K = 3;maxHeap = new ArrayList<>();maxHeap.add(null); // 在索引为0上添加空元素, array[0]位置不使用for(int i = 0; i<array.length; i++) {int size = getSize(); // 最大堆大小if( size < K ) { // maxHeap 未填满maxHeap.add( array[i] ); // 从后面追加插入新元素swim(size+1); //上浮, 对堆自下而上的有序化} else { // maxHeap 已填满Integer maxElement = maxHeap.get(1); // 获取堆中最大的元素if( array[i] < maxElement ) { // 新元素比堆中最大的元素还小maxHeap.set(1, array[i]); // 替换根节点元素sink(1, size); // 下沉, 对堆自上而下的有序化}}}// 移除索引为0上的空元素maxHeap.remove(0);System.out.println("Top " + K + " (Min) : " + maxHeap );}/*** 获取测试用例*/private static Integer[] getTestCase() {Integer[] caseArray = {3,7,10,1,4,9,8,5,2,6};return caseArray;}}
测试结果如下:
参考文献
算法(第4版) Robert Sedgewick、Kevin Wayne 著
计算机程序设计艺术(第3卷):排序与查找 高德纳(Donald E.Knuth) 著
觉得本文有帮助？请分享给更多人
关注「算法爱好者」加星标，修炼编程内功
好文章，我在看❤️