读书笔记——堆和堆排序

大家好，欢迎来到IT知识分享网。

堆简介

经典的十大排序算法中有一种算法叫做堆排序。堆排序是借助于堆这种特殊的数据结构来实现的一种排序算法。说起堆的时候大家脑海里的第一反应就是一个树状的数据结构。其实堆是一类数据结构的统称，堆有二叉堆，二项堆，斐波那契堆，左偏树等等。

堆排序就是借助于二叉堆（binary heap）来实现的。

二叉堆是完全二叉树，同时满足堆的特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，并且每个节点的左子树和右子树都是一个二叉堆。

当父节点的值总是大于或者等于任何一个子节点的时候称为最大堆或者大顶堆、大根堆。

当父节点的值总是小于或者等于任何一个子节点的时候被称为最小堆或者小顶堆、小根堆。

用人话来说就是，当最大值为父节点的时候，就是大顶堆。最小值为父节点的时候，就是小顶堆。又因为完全二叉树可以用数组来存储，所以堆也可以用数组来存储。

上图就是一个大顶堆，和它对应的数组存储结构。

堆的索引

既然可以用数组来存储，那么相应的完全可以用数组的下标做索引来对堆进行操作。

通过观察上面的二叉树，我们可以得出如下公式：

1. 当一个节点的下标为i的时，它的左节点下标为2*i+1；它的右节点下标为2*i+2;
2. 当长度为n时，堆树的最后一个非叶子节点的下标为n/2-1(例如上图中的C节点)

堆的调整

对堆结点做调整，使之符合堆的属性，这个动作叫做heapify。我们用大顶堆举例：调整时，一般是先用一个max指针指向父节点；然后用max指针指向的值和左节点比较，如果左节点值较大，max指向左节点，否则不动；接着用max指针值和右节点比较，如果右节点值较大max指向右节点，否则不动。最后，将max指向的值和父节点进行交换。

代码实现如下：

public void heapify(int[] array, int i){ int left = 2 * i +1;//获取到左节点下标 int right =2*i+2;//获取到右节点下标 int max = i;//让max指针指向父节点 if(array[left] > array[max]){ max = left;//如果左节点值较大，max指向左节点 } if(array[right] > array[max]){ max = right;//如果右节点值较大，max指向右节点 } swap(array, i, max); //交换max指向结点和父节点的值 }

这里有几个注意点：

1. 在第一次heapify的动作完成后，调换了max和父节点的位置。父节点被放在了max指向的节点上。该结点所在的堆熟悉可能会被破坏。因此要对该节点进行一次调整动作。即在swap动作后再增加一行heapify(array，max)；
2. 存在父节点已经是最大值的情况，所以在交换前需要判断一下max和i是否相等。不相等在调换。
3. 堆里的数据是个有限集合，它有大小。根据父节点i的下标无脑计算左右子节点会出现数组越界情况。

针对以上三个情况，对heapify函数做出调整，修改后的代码为：

public void heapify(int[] array, int i, int len){ int left = 2 * i +1;//获取到左节点下标 int right =2*i+2;//获取到右节点下标 int max = i;//让max指针指向父节点 if(left< len && array[left] > array[max]){ max = left;//如果左节点值较大，max指向左节点 } if(right<len && array[right] > array[max]){ max = right;//如果右节点值较大，max指向右节点 } if (max != i){ swap(array, i, max); //交换max指向结点和父节点的值 heapify(array, max, len);//对交换后的节点再做一次调整动作 } }

堆的建造

将一个无序数列如果构建为一个堆？因为叶子结点是自然不需要调整的，只要找到二叉树的最后一个非叶子节点，对其进行heapify操作。接着对倒数第二个非叶子节点进行heapify操作。如此类推直到调整完根节点。完成整个堆的构建。如下图所示：

代码实现如下：

private static void buildHeap(int[] array, int len) { int index = len / 2 - 1; //找到最后一个非叶子节点 for (int i = index; i >= 0; i--) { //从最后一个非叶子节点开始倒数 //对对应节点进行heapify调整动作 heapify(array, i, len); } }

堆排序

已上部分我们已经构建了一个大顶堆，并且知道最大值是根节点，存储在array[0]位置。借助于堆这些特性来实现排序就非常简单：

1. 构建一个大顶堆
2. 将根节点和最末尾的一个节点交换
3. 对根节点进行heapify操作，又因为最末尾的已经是最大值，属于有序数列。所以进行heapify操作时堆的大小减1

以上步骤用代码实现为：

private static void heapSort(int[] array) { buildHeap(array, array.length);//第一步构建大顶堆 for (int i = array.length - 1; i > 0; i--) { swap(array, 0, i);//第二步根节点和末尾节点值交换 heapify(array, 0, i-1);//第三步，对根节点进行调整操作 } }

完整的实现代码为：

private static void heapSort(int[] array) { buildHeap(array, array.length); for (int i = array.length - 1; i > 0; i--) { swap(array, 0, i); heapify(array, 0, i - 1); } } private static void buildHeap(int[] array, int len) { int index = len / 2 - 1; //找到最后一个非叶子节点 for (int i = index; i >= 0; i--) { //从最后一个非叶子节点开始倒数 //对对应节点进行heapify调整动作 heapify(array, i, len); } } public static void heapify(int[] array, int i, int len) { int left = 2 * i + 1;//获取到左节点下标 int right = 2 * i + 2;//获取到右节点下标 int max = i;//让max指针指向父节点 if (left < len && array[left] > array[max]) { max = left;//如果左节点值较大，max指向左节点 } if (right < len && array[right] > array[max]) { max = right;//如果右节点值较大，max指向右节点 } if (max != i) { swap(array, i, max); //交换max指向结点和父节点的值 heapify(array, max, len);//对交换后的节点再做一次调整动作 } } private static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; }

堆排序算法分析

时间复杂度

• 堆排序是创建堆+堆调整加在一起完成的。
• 构建堆的时间复杂度为O(n)；堆单次调整时间复杂度为logn，n-1个节点调整下来整体的时间复杂度为n*logn；所以堆排序的时间复杂度为O(n+nlogn) = O(nlogn)
• 详细的推导可以参考这里：https://chihminh.github.io/2016/08/08/heap-sort/。这里只记录结论。

空间复杂度

• 因为堆排序是在原地完成的，所以它的空间复杂度为O(1)

稳定性

• 我们知道堆的结构是节点i的孩子为2i和2i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n /2-1, n/2-2, …1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没 有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序是不稳定的排序算法。

备注：

针对堆的这些特性，堆一般会被应用到这些场景：

1. 排序，堆排序
2. 优先级队列，PriorityBlockingQueue。
3. 海量数据中查找前k个大（或者前k个小）数。