厦门建站价格,wordpress 古今,网站转跳怎么做,网站开发趋势完全二叉树 完全二叉树中如果每棵子树的最大值都在顶部就是大根堆 完全二叉树中如果每棵子树的最小值都在顶部就是小根堆 设计目标#xff1a;完全二叉树的设计目标是高效地利用存储空间#xff0c;同时便于进行层次遍历和数组存储。它的结构使得每个节点的子节点都可以通过简…完全二叉树 完全二叉树中如果每棵子树的最大值都在顶部就是大根堆 完全二叉树中如果每棵子树的最小值都在顶部就是小根堆 设计目标完全二叉树的设计目标是高效地利用存储空间同时便于进行层次遍历和数组存储。它的结构使得每个节点的子节点都可以通过简单的计算得到从而实现快速的节点访问。
实现原理完全二叉树是一棵满二叉树除了最后一层外每一层都被完全填充。最后一层的节点都集中在左边。这种结构可以用数组来存储其中数组的索引对应节点的位置。例如对于索引为i的节点其左子节点的索引为2i1右子节点的索引为2i2父节点的索引为(i-1)/2。
优点空间利用率高易于实现数组存储。层次遍历简单可以通过数组索引快速访问节点。
缺点插入和删除节点可能比较耗时特别是当需要保持完全二叉树的结构时可能需要重新调整整个结构。
堆结构 堆结构就是用数组实现的完全二叉树结构 设计目标堆结构的设计目标是实现高效的优先级队列和排序算法。它基于完全二叉树的结构通过维护堆序性父节点的值大于或等于子节点的值或者小于或等于子节点的值来实现快速的插入和删除操作。
实现原理堆结构通常用数组来实现其中数组的索引对应节点的位置。在堆中每个父节点的值都满足一定的条件例如最大堆中父节点的值大于或等于子节点的值最小堆中父节点的值小于或等于子节点的值。插入操作通过在数组末尾添加元素然后通过上浮Percolate Up来维护堆序性。删除操作通常是指删除堆顶元素然后通过下沉Percolate Down来维护堆序性。
优点插入和删除操作的时间复杂度为O(log n)在优先级队列和排序算法中性能优越。空间利用率高用数组实现简单。
缺点对于范围查询等操作不友好无法高效地进行任意元素的查找和删除操作。 如何理解“堆” 堆本质是一种特殊的树。关于这个树只要满足两点要求它就是一个堆 堆是一个完全二叉树堆中每一个节点的值都必须大于等于或小于等于其子树中每个节点的值。 第一点堆必须是一个完全二叉树。完全二叉树要求除了最后一层其他层的节点个数都是满的最后一层的节点都靠左排列。 第二点堆中的每个节点的值必须大于等于或者小于等于其子树中每个节点的值。实际上我们还可以换一种说法堆中每个节点的值都大于等于或者小于等于其左右子节点的值。这两种表述是等价的。 对于每个节点的值都大于等于子树中每个节点值的堆我们叫作“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆我们叫作“小顶堆”。 堆结构的heapInsert操作
将一个新元素插入到堆结构中并维持堆的性质即父节点的值大于或等于子节点的值或者小于或等于子节点的值视堆的类型而定。
示例
假设有一个最大堆堆数组为 [100, 85, 90, 80, 75, 70]现在需要插入元素 95。 插入后数组变为 [100, 85, 90, 80, 75, 70, 95]。 新元素的位置是 6从 0 开始计数。 比较新元素与父节点位置 (6-1)/22值 9095 90交换两者位置数组变为 [100, 85, 95, 80, 75, 70, 90]。 继续比较新元素与新的父节点位置 (2-1)/20值 10095 100无需交换。 插入完成堆性质得以维持。
优点能够在 O(log n) 时间复杂度内完成插入操作。
缺点需要调整堆的结构可能导致多次数据交换。
堆结构的heapify操作
在堆结构中当某个节点的子节点可能违反堆的性质时通过调整该节点及其子节点维持堆的性质。
示例
假设有一个最大堆堆数组为 [95, 85, 90, 80, 75, 70]现在需要对位置 0 的节点进行 heapify 操作。 该节点的值为 95子节点为 85 和 90。 95 大于子节点无需调整。 如果堆数组为 [75, 85, 90, 80, 75, 70]需要对位置 0 的节点进行 heapify。 比较子节点 85 和 90选择较大的 90 作为候选。 交换 75 和 90数组变为 [90, 85, 75, 80, 75, 70]。 继续 heapify 位置 2 的节点原来的 75。 比较子节点 80 和 75交换 75 和 80数组变为 [90, 85, 80, 75, 75, 70]。 继续 heapify 位置 3 的节点原来的 75没有子节点调整完成。
优点能够在 O(log n) 时间复杂度内完成调整操作。
缺点需要遍历节点的子节点可能导致多次数据交换。
堆结构的增大
当堆中的元素数量增加需要扩展堆的存储空间。 通常使用动态数据结构如动态数组或链表来实现堆的动态增长。 当需要增大堆时分配新的内存空间并将原堆中的元素复制到新空间中。
示例
假设堆当前的存储数组大小为 10已满。需要插入一个新元素堆将自动增大到大小为 20。
堆结构的减少
当堆中的元素数量减少可能需要缩小堆的存储空间以节省内存。 释放堆中多余的存储空间调整存储数组的大小。 可以通过动态数据结构的特性如动态数组的收缩功能实现堆的缩小。
示例
假设堆当前的存储数组大小为 20但只有 5 个元素。可以将堆缩小到大小为 10释放多余的空间。
优先级队列结构
设计目标
优先级队列的设计目标是允许高效地访问和操作优先级最高的元素。与普通队列中的先进先出FIFO原则不同优先级队列中的元素根据其优先级进行排序并且优先级最高的元素会被优先处理。
实现原理
优先级队列通常使用堆结构来实现能够高效地维护元素的优先级顺序。
1. 插入操作Enqueue
将新元素添加到堆的末尾。
通过上浮Percolate Up操作将新元素与父节点进行比较和交换直到满足堆的性质。
2. 删除操作Dequeue
删除堆顶元素优先级最高的元素。
将堆的最后一个元素移动到堆顶。
通过下沉Percolate Down操作将该元素与子节点进行比较和交换直到满足堆的性质。
优点
插入和删除操作的时间复杂度为 O(log n)在需要动态维护优先级的场景中性能优越。
空间利用率高可以用数组实现节省存储空间。
缺点
不支持高效的随机访问和查询操作无法快速找到任意元素。
对于某些操作如批量插入可能需要重新构建整个堆导致较高的开销。
堆排序
堆排序是一种原地的、时间复杂度为O(n log n)的排序算法。
堆排序不是稳定的排序算法因为在排序的过程存在将堆的最后一个节点跟堆顶节点互换的操作所以就有可能改变值相同数据的原始相对顺序。
实现步骤 先让整个数组都变成大根堆结构建立堆的过程: 从上到下的方法时间复杂度为O(N * logN) 从下到上的方法时间复杂度为O(N) 把堆的最大值和堆末尾的值交换然后减少堆的大小之后再去调整堆一直周而复始时间复杂度为O(N * logN) 堆的大小减小成0之后排序完成
实现代码 /*** 对给定的整数数组进行堆排序。* 堆排序是一种基于堆数据结构的排序算法它的时间复杂度为O(N log N)空间复杂度为O(1)。** param arr 待排序的整数数组*/public void heapSort(int[] arr) {// 如果数组为空或者长度小于2直接返回因为不需要排序if (arr null || arr.length 2) {return;}// O(N*logN)// 从数组的最后一个元素开始依次将每个元素调整为大根堆for (int i arr.length - 1; i 0; i--) {heapify(arr, i, arr.length);}// 初始化堆的大小为数组的长度int heapSize arr.length;// 将堆顶元素最大值与堆的最后一个元素交换并将堆的大小减1swap(arr, 0, --heapSize);// O(N*logN)// 当堆的大小大于0时继续进行排序while (heapSize 0) { // O(N)// 将堆顶元素调整为大根堆heapify(arr, 0, heapSize); // O(logN)// 将堆顶元素最大值与堆的最后一个元素交换并将堆的大小减1swap(arr, 0, --heapSize); // O(1)}}/*** 将指定索引位置的元素插入到堆中并调整堆结构使其满足大根堆的性质。* 该方法会将新元素与其父节点比较如果新元素大于父节点则交换它们的位置* 并继续向上比较直到新元素小于等于父节点或到达堆顶。** param arr 包含堆元素的数组* param index 要插入的元素的索引*/public void heapInsert(int[] arr, int index) {// 当当前元素大于其父节点时交换它们的位置并更新当前元素的索引while (arr[index] arr[(index - 1) / 2]) {swap(arr, index, (index - 1) / 2);index (index - 1) / 2;}}/*** 调整指定索引位置的元素使其满足大根堆的性质。* 该方法会将指定元素与其子节点比较如果该元素小于其子节点中的最大值* 则交换它们的位置并继续向下比较直到该元素大于等于其子节点或到达叶子节点。** param arr 包含堆元素的数组* param index 要调整的元素的索引* param heapSize 当前堆的大小*/public void heapify(int[] arr, int index, int heapSize) {// 计算左孩子的下标int left index * 2 1; // 当左孩子存在时继续循环while (left heapSize) { // 两个孩子中谁的值大把下标给largest// 1只有左孩子left - largest// 2) 同时有左孩子和右孩子右孩子的值 左孩子的值left - largest// 3) 同时有左孩子和右孩子并且右孩子的值 左孩子的值 right - largest// 找出左右孩子中值较大的那个的下标int largest left 1 heapSize arr[left 1] arr[left] ? left 1 : left;// 比较父节点和较大孩子的值将较大值的下标赋给largestlargest arr[largest] arr[index] ? largest : index;// 如果父节点已经是最大的跳出循环if (largest index) {break;}// 交换父节点和较大孩子的位置swap(arr, largest, index);// 更新当前节点的下标index largest;// 计算新的左孩子的下标left index * 2 1;}}/*** 交换数组中两个指定索引位置的元素。** param arr 包含元素的数组* param i 第一个元素的索引* param j 第二个元素的索引*/public void swap(int[] arr, int i, int j) {// 使用临时变量交换两个元素的值int tmp arr[i];arr[i] arr[j];arr[j] tmp;}过程分析
我们可以把堆排序的过程大致分解成两个大的步骤建堆和排序。
建堆
我们首先将数组原地建成一个堆。所谓“原地”就是不借助另一个数组就在原数组上操作。建堆的过程有两种思路。
第一种是在堆中插入一个元素。尽管数组中包含个数据但是我们可以假设起初堆中只包含一个数据就是下标为1的数据。然后我们调用插入操作将下标从2到n的数据依次插入到堆中。这样我们就将包含n个数据的数组组织成了堆。
第二种实现思路跟第一种截然相反。第一种建堆思路的处理过程是从前往后处理数组数据并且每个数据插入堆中时都是从下往上堆化。而第二种实现思路是从后往前处理数组并且每个数据都是从上往下堆化。
逐层调整直到整个数组满足堆的条件。
从最后一个非叶子节点开始逐层向上进行 heapify 操作。最后一个非叶子节点的索引为floor((n-2)/2)其中 n 是数组的长度。使用 heapify 调整以该节点为根的子树。
排序
建堆结束之后数组中的数据已经是按照大顶堆的特性来组织的。数组中的第一个元素就是堆顶也就是最大的元素。我们把它跟最后一个元素交换那最大元素就放到了下标为n的位置。
当堆顶元素移除之后我们把下标为n的元素放到堆顶然后再通过堆化的方法将剩下的n1个元素重新构建成堆。堆化完成之后我们再取堆顶的元素放到下标是n一1的位置一直重复这个过程直到最后堆中只剩下标为1的一个元素排序工作就完成了。
为什么快速排序要比堆排序性能好
堆排序数据访问的方式没有快速排序友好
快速排序的数据访问方式 快速排序是基于分治法Divide and Conquer的排序算法。它通过选择一个基准值pivot将数组划分为两个子数组左侧子数组的元素小于或等于基准值右侧子数组的元素大于或等于基准值。然后递归地对这两个子数组进行排序。在分割过程中快速排序对数组中的元素进行连续的比较和交换这种操作在内存中的数据访问模式通常是连续的与现代计算机的缓存机制非常匹配。连续的内存访问使得缓存命中率更高减少了内存访问的延迟从而提高了排序的效率。 例如当对一个已部分排序的数组进行快速排序时基准值的选择和分割操作会使得数组被分割为较小的子数组而这些子数组在内存中是连续存储的。对这些子数组进行递归排序时缓存能够有效地预取cache prefetch这些连续的数据减少了从主存中加载数据的次数加快了排序的速度。
堆排序的数据访问方式 堆排序依赖于堆数据结构需要频繁地访问父节点和子节点。在堆排序过程中数据的访问模式是随机的无法充分利用内存的局部性原理。堆的父节点和子节点在内存中可能不是连续存储的因此访问这些节点时常常会导致缓存未命中。缓存未命中会增加内存访问的延迟降低排序的效率。 例如在调整堆结构时需要比较父节点和子节点的值并根据比较结果进行交换。这种访问模式使得数据在内存中的跳转较为频繁无法像快速排序那样利用缓存的预取特性导致性能下降。
对于同样的数据在排序过程中堆排序算法的数据交换次数要多于快速排序
快速排序的数据交换次数 快速排序的平均时间复杂度为O(n log n)其数据交换次数相对较少。在快速排序的分割过程中每个元素会被交换到正确的位置但整个过程中交换的次数通常比堆排序少。快速排序的递归结构使得大部分元素的比较和交换发生在较小的子数组中减少了不必要的数据移动。 例如对一个随机分布的数组进行快速排序时每次分割操作会使得元素被快速地放置在接近其最终位置的地方。这减少了后续排序过程中需要移动的数据量从而降低了数据交换的总次数。
堆排序的数据交换次数 堆排序的主要操作是构建堆和调整堆结构。在构建堆的过程中需要多次比较和交换元素。每次插入或删除元素时堆结构的维护需要进行多次比较和交换以确保父节点的值大于或等于子节点的值对于最大堆而言。在堆排序的整个过程中数据交换的次数相对较多。 例如当构建一个最大堆时每个元素都需要与它的子节点进行比较和交换。如果一个元素的值小于它的子节点中的较大者就需要交换它们的位置并继续对子节点进行调整。这个过程会涉及到多次数据交换直到堆的性质被满足。在堆排序的调整过程中这样的交换操作会频繁发生导致数据交换次数增加从而影响了排序的性能。
