怎么压缩网站,wordpress 别名一致,龙岗企业网站设计公司,什么是电子商务网站建设数组、链表都是一维的数据结构#xff0c;相对来说比较容易理解#xff0c;而堆是二维的数据结构#xff0c;对抽象思维的要求更高#xff0c;所以许多程序员「谈堆色变」。但堆又是数据结构进阶必经的一步#xff0c;我们不妨静下心来#xff0c;将其梳理清楚。 堆… 数组、链表都是一维的数据结构相对来说比较容易理解而堆是二维的数据结构对抽象思维的要求更高所以许多程序员「谈堆色变」。但堆又是数据结构进阶必经的一步我们不妨静下心来将其梳理清楚。 堆符合以下两个条件之一的完全二叉树 根节点的值 ≥ 子节点的值这样的堆被称之为最大堆或大顶堆根节点的值 ≤ 子节点的值这样的堆被称之为最小堆或小顶堆。 堆排序的思想是由 J. W. J. Williams 在1964 年发明的。
堆排序过程如下
用数列构建出一个大顶堆取出堆顶的数字调整剩余的数字构建出新的大顶堆再次取出堆顶的数字循环往复完成整个排序。
整体的思路就是这么简单我们需要解决的问题有两个
如何用数列构建出一个大顶堆取出堆顶的数字后如何将剩余的数字调整成新的大顶堆。 构建大顶堆 调整堆
构建大顶堆有两种方式
方案一从 0 开始将每个数字依次插入堆中一边插入一边调整堆的结构使其满足大顶堆的要求方案二将整个数列的初始状态视作一棵完全二叉树自底向上调整树的结构使其满足大顶堆的要求。 在介绍堆排序具体实现之前我们先要了解完全二叉树的几个性质。将根节点的下标视为 0则完全二叉树有如下性质
对于完全二叉树中的第 i 个数它的左子节点下标left 2i 1对于完全二叉树中的第 i 个数它的右子节点下标right left 1对于有 n 个元素的完全二叉树(n≥2)它的最后一个非叶子结点的下标n/2 - 1
堆排序代码如下
public static void heapSort(int[] arr) {// 构建初始大顶堆buildMaxHeap(arr);for (int i arr.length - 1; i 0; i--) {// 将最大值交换到数组最后swap(arr, 0, i);// 调整剩余数组使其满足大顶堆maxHeapify(arr, 0, i);}
}
// 构建初始大顶堆
private static void buildMaxHeap(int[] arr) {// 从最后一个非叶子结点开始调整大顶堆最后一个非叶子结点的下标就是 arr.length / 2-1for (int i arr.length / 2 - 1; i 0; i--) {maxHeapify(arr, i, arr.length);}
}
// 调整大顶堆第三个参数表示剩余未排序的数字的数量也就是剩余堆的大小
private static void maxHeapify(int[] arr, int i, int heapSize) {// 左子结点下标int l 2 * i 1;// 右子结点下标int r l 1;// 记录根结点、左子树结点、右子树结点三者中的最大值下标int largest i;// 与左子树结点比较if (l heapSize arr[l] arr[largest]) {largest l;}// 与右子树结点比较if (r heapSize arr[r] arr[largest]) {largest r;}if (largest ! i) {// 将最大值交换为根结点swap(arr, i, largest);// 再次调整交换数字后的大顶堆maxHeapify(arr, largest, heapSize);}
}
private static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;
} 堆排序的第一步就是构建大顶堆对应代码中的 buildMaxHeap 函数。我们将数组视作一颗完全二叉树从它的最后一个非叶子结点开始调整此结点和其左右子树使这三个数字构成一个大顶堆。 调整过程由 maxHeapify 函数处理 maxHeapify 函数记录了最大值的下标根结点和其左右子树结点在经过比较之后将最大值交换到根结点位置。这样这三个数字就构成了一个大顶堆。 需要注意的是如果根结点和左右子树结点任何一个数字发生了交换则还需要保证调整后的子树仍然是大顶堆所以子树会执行一个递归的调整过程。 这里的递归比较难理解我们打个比方构建大顶堆的过程就是一堆数字比赛谁更大。比赛过程分为初赛、复赛、决赛每场比赛都是三人参加。但不是所有人都会参加初赛只有叶子结点和第一批非叶子结点会进行三人组初赛。初赛的冠军站到三人组的根结点位置然后继续参加后面的复赛。 而有的人生来就在上层比如李小胖它出生在数列的第一个位置上是二叉树的根结点当其他结点进行初赛、复赛时它就静静躺在根结点的位置等一场决赛。 当王大强和张壮壮经历了重重比拼来到了李小胖的左右子树结点位置。他们三个人开始决赛。王大强和张壮壮是靠实打实的实力打上来的他们已经确认过自己是小组最强。而李小胖之前一直躺在这里等决赛。如果李小胖赢了他们两个说明李小胖是所有小组里最强的毋庸置疑他可以继续坐在冠军宝座。 但李小胖如果输给了其中任何一个人比如输给了王大强。王大强会和张壮壮对决选出本次构建大顶堆的冠军。但李小胖能够坐享其成获得第三名吗生活中或许会有这样的黑幕但程序不会欺骗我们。李小胖跌落神坛之后就要从王大强的打拼路线回去继续向下比较找到自己真正实力所在的真实位置。这就是 maxHeapify 中会继续递归调用 maxHeapify 的原因。 当构建出大顶堆之后就要把冠军交换到数列最后深藏功与名。来到冠军宝座的新人又要和李小胖一样开始向下比较找到自己的真实位置使得剩下的 n−1 个数字构建成新的大顶堆。这就是 heapSort 方法的 for 循环中调用 maxHeapify 的原因。 变量 heapSize 用来记录还剩下多少个数字没有排序完成每当交换了一个堆顶的数字heapSize 就会减 1。在 maxHeapify 方法中使用 heapSize 来限制剩下的选手不要和已经躺在数组最后当过冠军的人比较免得被暴揍。 这就是堆排序的思想。学习时我们采用的是最简单的代码实现在熟练掌握了之后我们就可以加一些小技巧以获得更高的效率。比如我们知道计算机采用二进制来存储数据数字左移一位表示乘以 2右移一位表示除以 2。所以堆排序代码中的arr.length / 2 - 1 可以修改为 (arr.length 1) - 1左子结点下标2 * i 1可以修改为(i 1) 1。需要注意的是位运算符的优先级比加减运算的优先级低所以必须给位运算过程加上括号。 注在有的文章中作者将堆的根节点下标视为 1这样做的好处是使得第 i 个结点的左子结点下标为 2i右子结点下标为 2i 1与 2i 1 和 2i 2 相比计算量会少一点本文未采取这种实现但两种实现思路的核心思想都是一致的。 分析可知堆排序是不稳定的排序算法。 时间复杂度 空间复杂度 堆排序分为两个阶段初始化建堆buildMaxHeap和重建堆maxHeapify直译为大顶堆化。所以时间复杂度要从这两个方面分析。 根据数学运算可以推导出初始化建堆的时间复杂度为 O(n)重建堆的时间复杂度为 O(nlogn)所以堆排序总的时间复杂度为 O(nlogn)。推导过程较为复杂故不再给出证明过程。 堆排序的空间复杂度为 O(1)只需要常数级的临时变量。 堆排序是一个优秀的排序算法但是在实际应用中快速排序的性能一般会优于堆排序。
