当前位置: 首页> 汽车> 车展 > 事件营销定义_镇江扬中新闻网_seo职业培训学校_网站推广基本方法是

事件营销定义_镇江扬中新闻网_seo职业培训学校_网站推广基本方法是

时间:2025/7/11 0:17:15来源:https://blog.csdn.net/2301_78696090/article/details/146567726 浏览次数: 0次
事件营销定义_镇江扬中新闻网_seo职业培训学校_网站推广基本方法是

堆排序

        堆排序就是利用堆的思想来对数据进行排序,其实主要就分为两个步骤,即建堆和堆的删除。

概念解惑

        在正式介绍如何排序之前,先理清一些基本的操作,如什么时候用向上调整,什么时候用向下调整,以及分别在什么操作下对应什么位置来进行这些调整。       

         在堆排序中,构建大顶堆时确实使用向下调整(Heapify Down),但需要明确调整的起始点调整方向的区别。

1. 向下调整(Heapify Down)的本质

  • 调整方向:从某个节点向下与其子节点比较,确保父节点 ≥ 子节点(最大堆)。

  • 起始点:构建堆时,从最后一个非叶子节点开始,自底向上遍历所有非叶子节点。

    • 为什么是最后一个非叶子节点?
      完全二叉树中,最后一个非叶子节点的下标为 n/2 - 1n 是数组长度)。这些节点是“潜在不满足堆性质”的最小单元,调整它们可以高效构建堆。

    • 处理顺序:从最后一个非叶子节点(最底层)向根节点方向逐个处理。

以这个二叉树为例子:

  • 最后一个非叶子节点是值为 2 的节点(下标 2)。

  • 调整顺序:先处理 2,再处理 5,最后处理根节点 3

2. 向上调整(Heapify Up)的本质

  • 调整方向:从某个节点(通常是新插入的叶子节点)向上与其父节点比较,确保子节点 ≤ 父节点(最大堆)。

  • 起始点:插入新元素时,从新插入的叶子节点开始,逐步向上调整到根。

    • 适用场景:适合动态插入元素到已有堆中(如优先队列)。

    • 时间复杂度:每次插入需 O(log n) 时间,构建堆需 O(n log n)。

3. 代码对比:构建堆的两种方式

方式1:向下调整(正确且高效)

void buildMaxHeap(int arr[], int n) {
    // 从最后一个非叶子节点开始,逆序处理所有非叶子节点
    for (int i = n/2 - 1; i >= 0; i--) {
        heapifyDown(arr, n, i); // 对每个非叶子节点向下调整
    }
}

//时间复杂度:O(n)

方式2:向上调整(低效,仅用于插入)

void buildMaxHeapWrong(int arr[], int n) {
    // 错误示范:逐个插入元素,从叶子节点向上调整
    for (int i = 0; i < n; i++) {
        heapifyUp(arr, i); // 对每个新插入的节点向上调整
    }
}

//时间复杂度:O(n log n)(效率低,不推荐用于构建堆)

4.直观总结

 这张图可以很好地概括这些问题:

5. 为什么构建堆不用向上调整?

  • 数学证明:向下调整的时间复杂度为 O(n),而向上调整需要 O(n log n)。

  • 直观理解:叶子节点占总数的一半,调整叶子节点无意义(它们没有子节点)。向下调整从非叶子节点开始,减少了冗余操作。

堆排序原理

        堆排序是一种高效的排序算法,利用二叉堆(通常为最大堆)数据结构实现。其核心思想是通过构建堆结构,反复提取最大元素并调整剩余部分,最终得到有序序列。

  1. 构建堆:将无序数组调整为最大堆(父节点值 ≥ 子节点值)(升序:建大堆 ,降序:建小堆)

  2. 排序阶段

    • 交换堆顶(最大值)与当前末尾元素。

    • 缩小堆范围,重新调整剩余元素为最大堆。

    • 重复上述步骤,直到所有元素有序。

简要实现(升序)

向下调整方法(递归版)

#include <stdio.h>// 交换元素
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}// 调整以i为根的子树为最大堆
void heapify(int arr[], int n, int i) {int largest = i;         // 初始化最大元素为根int left = 2 * i + 1;    // 左子节点int right = 2 * i + 2;   // 右子节点// 若左子节点大于根if (left < n && arr[left] > arr[largest])largest = left;// 若右子节点大于当前最大值if (right < n && arr[right] > arr[largest])largest = right;// 若最大值不是根,交换并递归调整if (largest != i) {swap(&arr[i], &arr[largest]);heapify(arr, n, largest);}
}

堆排序

// 堆排序主函数
void heapSort(int arr[], int n) {// 构建最大堆(从最后一个非叶子节点开始)for (int i = n / 2 - 1; i >= 0; i--)heapify(arr, n, i);// 逐个提取元素for (int i = n - 1; i > 0; i--) {swap(&arr[0], &arr[i]);     // 将最大值移到末尾heapify(arr, i, 0);          // 调整剩余部分为堆}
}

堆排序的适用场景

  • 优点

    • 时间复杂度稳定,始终为 O(nlog⁡n)。

    • 空间复杂度为O(1),适合内存有限的环境。

  • 构建堆阶段:O(n)

  • 排序阶段:O(n log n)

  • 总时间复杂度:O(n) + O(n log n) = O(n log n)

无论是平均还是最坏情况,排序阶段的 O(n log n) 主导总时间复杂度,因此堆排序的时间复杂度稳定为 O(n log n)

堆排序的时间复杂度与输入数据的初始顺序无关:

  • 构建堆阶段:无论数据是否有序,都需要遍历所有非叶子节点调整。

  • 排序阶段:每次提取堆顶后,必须从根节点向下调整,调整次数固定为树的高度(log n)。

因此,最坏情况与平均情况时间复杂度一致,均为 O(n log n)。

  • 缺点

    • 不是稳定的排序算法(相同的元素可能会改变相对顺序)。

    • 对于小规模数据,可能不如插入排序等简单算法高效。

适用场景

  • 数据量较大且对稳定性要求不高的场景。

  • 需要原地排序(不占用额外空间)的场景。

  • 实时性要求较高的场景(如嵌入式系统、实时排序等)。

关键字:事件营销定义_镇江扬中新闻网_seo职业培训学校_网站推广基本方法是

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: