html5 微网站开发网站定制开发是什么

html5 微网站开发,网站定制开发是什么,福清网站建设专家,品牌规划前言#xff1a;堆排序#xff08;Heap Sort#xff09;是一种基于二叉堆#xff08;Binary Heap#xff09; 数据结构的比较排序算法。它的核心思想利用了堆这种数据结构“能快速找到最大值#xff08;或最小值#xff09;”的特性。一、建堆建堆算法是将无序数组转化为…前言堆排序Heap Sort是一种基于二叉堆Binary Heap 数据结构的比较排序算法。它的核心思想利用了堆这种数据结构“能快速找到最大值或最小值”的特性。一、建堆建堆算法是将无序数组转化为符合“堆规则”的完全二叉树逻辑结构的核心方法是堆排序、Top K等所有堆应用的基础相比于通过数据结构中堆的插入建堆需要额外O(N)的空间复杂度基于数组原地实现建堆仅需要O(1)的空间复杂度。1.1向上调整算法的回顾场景实例假设现在存在一个小堆要向堆中插入一个元素并维持堆的结构。核心逻辑新元素插入堆尾后它的父节点可能比新插入子节点小 —— 让新元素“ 上浮 ”与父节点交换直到它比父节点小或浮到根节点堆顶。简而言之对于向上调整算法的核心思维就是当子节点可能比父节点 “更合适”时需要让子节点往上浮找到合适位置。实例分析一、如上图所示由于新插入的子节点的值为 10 与 其父亲节点的值 28 相比 不满足小堆的关系所以我们需要让子节点向上浮动直到它比父节点更小或者一直向上浮动到根节点为止。二、详解向上调整的过程( 1 ) 上图中原来的小堆为: [15 , 18 , 19 , 25 , 28 , 34 , 65 , 49 , 27 , 37] 堆中元素个数size10现需要插入一个元素 10 放在堆尾索引为10的位置处( 2 ) 新插入的子节点的索引为 child 10 插入后小堆变为 [15 , 18 , 19 , 25 , 28 , 34 , 65 , 49 , 27 , 3710]计算得到其父亲节点的索引为 parent( child - 1 ) / 2 , 即索引为4 arr[4]28。( 3 )比较arr[child] 与 arr[parent] 的值由于要维持小堆所以当arr[child] arr [parent] 时就要对子节点和父亲节点进行交换交换后的小堆变为 [15 , 18 , 19 , 25 , 10 , 34 , 65 , 49 , 27 , 3728]( 4 )更新孩子节点的索引和父亲节点的索引childparent ; parent(child-1) / 2 ;( 5 ) 重复这个过程直到满足新插入的子节点比父节点更小或者一直向上浮动到根节点为止所以我们可以通过循环进行描述上述三个步骤。三、向上调整算法的应用void AdjustUp(HPDataType* a, int child) { //已知孩子节点的下标为child //父亲节点下标为:(child-1)/2 //初始时父亲节点的下标 int parent (child - 1) / 2; while (child 0) { if (a[child] a[parent]) { //进行交换 swap(a[child], a[parent]); //更新孩子节点的下标 child parent; //更新父亲节点的下标 parent (child - 1) / 2; } else { break; } } //退出条件为 //1.子节点比父节点大 //2.子节点到达根的位置 }四、若原来是大堆只需把比较符号反转,将 “” 变为 “”, 即当前节点 父节点大根堆性质破坏则交换并继续上浮。1.2利用向上调整算法建堆基于向上调整算法的思想我们可以对任何一个数组进行建堆大堆或小堆通过循环传入数组中的每个元素及其下标相当于对数组中的每个元素进行向上调整即完成了建堆。代码示例void swap(int *a,int *b) { int tmp*a; *a*b; *btmp; } //向上调整算法 void AdjustUp(HPDataType* a, int child) { //已知孩子节点的下标为child //父亲节点下标为:(child-1)/2 //初始时父亲节点的下标 int parent (child - 1) / 2; while (child 0) { if (a[child] a[parent]) { //进行交换 swap(a[child], a[parent]); //更新孩子节点的下标 child parent; parent (child - 1) / 2; } else { break; } } } void PrintArray(int arr[], int size) { for (int i 0; i size; i) { printf(%d , arr[i]); } } int main() { int arr[] { 9,6,4,7,5,3,2,1 }; int size sizeof(arr) / sizeof(arr[0]); printf(建堆前的数组: \n); PrintArray(arr, size); for (int i 0; i size; i) { AdjustUp(arr, i); } printf(\n建堆后的数组\n); PrintArray(arr, size); return 0; }如下图所示建堆时间复杂度分析:由于堆是一棵完全二叉树对于完全二叉树的高度h满足h≈log2(N) 最坏的情况下需要从叶节点一直到根节点向上浮动h次故而向上调整算法的时间复杂度为OlogN。对于一个数组而言有N个元素即有N个节点每个节点的最坏情况都是需要从叶节点到根节点故而向上调整算法建堆的时间复杂度为O(N*logN)1.3 向下调整算法的回顾场景实例假设现在存在一个小堆若堆顶元素被一个更大的值替代并维持堆的结构。核心思维当父节点位置可能比子节点位置“不合适”时需要让父节点往下沉找到合适位置。实例分析一、如上图所示原堆顶元素5被更大的元素27替换后破坏了小堆性质。此时父节点位置已不满足条件所以需要通过向下调整操作直到它比子节点更小或者到达叶节点位置温馨提示判断是否到达叶节点位置即只需要判断其子节点不在堆的范围内循环的停止条件。二、详解向下调整的过程( 1 ) 上图中原来的小堆为[5151918283465492537] 但是堆顶元素被替换为27则现在的小堆变为[27151918283465492537],此时堆中的元素不在满足小堆的特性,需要进行向下调整。( 2 ) 此时父亲节点的索引为parent0其左孩子节点的索引为leftchildparent * 2 1 其右孩子节点的索引为rightchildparent*22。我们不能确定左孩子节点的值与右孩子节点的值的大小关系所以需要进行比较确定出其中最小的一个。这里可以通过假设法不用单独区分左孩子节点的索引和右孩子节点的索引只需定义一个子节点索引child然后假设左孩子节点的值最小若左孩子节点的值大于右孩子节点的值即右孩子节点的更小仅需要对child即可找到右孩子节点。( 3 ) 比较arr[parent]与arr[child]的值由于需要维持小堆如果arr[parent]arr[child],需要对父节点和子节点进行交换。交换后的小堆为[15271918283465492537]( 4 ) 更新parent的索引和child的索引parentchild; childparent * 2 1;( 5 ) 重复这个过程直到它比子节点更小或者到达叶节点位置叶节点位置处满足子节点不在堆的范围内。三、向下调整代码的实现void AdjustDown(HPDataType* a, int size, int parent) { //父亲节点下标parent //左孩子节点下标为parent*21 //右孩子节点下标为parent*22 //假设左孩子是最小的 int child parent * 21; while (child size) { //保证child1在有效范围 if (child1 size a[child 1] a[child] ) { child; } if (a[child] a[parent]) { //交换父亲节点和孩子节点 swap(a[child], a[parent]); //更新父亲节点 parent child; //更新孩子节点 child parent * 2 1; } else { break; } } //退出循环的条件 //1.父节点无子节点即到达了叶节点位置通过不满足while循环条件退出 //2.父节点的值 子节点的值通过break退出 }四、若原来是大堆只需把比较符号反转,将 “” 变为 “”, 即当前节点 父节点大根堆性质破坏则交换并继续下浮。1.4利用向下调整算法建堆向下调整能建堆本质是利用 “ 完全二叉树的特性 ”“ 从后向前 ” 的调整顺序让每个非叶子节点调整后其所在的子树都符合堆规则最终扩散到整个树形成完整堆。这是一种局部到整体的思维对于叶子节点而言其可以被视为堆所以只需要对非叶子节点所在的子树进行向下调整直到每个节点所在的子树都满足堆的特性即完成了建堆。代码示例void swap(int *a,int *b) { int tmp*a; *a*b; *btmp; } void AdjustDown(int* a, int size, int parent) { //父亲节点下标parent //左孩子节点下标为parent*21 //右孩子节点下标为parent*22 //假设左孩子是最小的 int child parent * 21; while (child size) { //保证child1在有效范围 if (child1 size a[child 1] a[child] ) { child; } if (a[child] a[parent]) { //交换父亲节点和孩子节点 swap(a[child], a[parent]); //更新父亲节点 parent child; //更新孩子节点 child parent * 2 1; } else { break; } } //退出循环的条件 //1.父节点无子节点即到达了叶节点位置通过不满足while循环条件退出 //2.父节点的值 子节点的值通过break退出 } void PrintArray(int arr[], int size) { for (int i 0; i size; i) { printf(%d , arr[i]); } } int main() { int arr[] { 9,6,4,7,5,3,2,1 }; int size sizeof(arr) / sizeof(arr[0]); printf(建堆前的数组: \n); PrintArray(arr, size); for (int i (size-1-1)/2; i0 ; i--) { AdjustDown(arr, size, i); } printf(\n建堆后的数组\n); PrintArray(arr, size); return 0; }如图所示时间复杂度分析: 以满二叉为例对于向下调整算法建堆时间复杂度为O(N)分析如下所示二、堆排序堆是堆排序的 核心数据结构其核心价值是“ 高效维护最大值 或 最小值 ”堆排序的所有逻辑都围绕堆的这一特性展开本质是把 “ 无序数组 ” 通过堆转化为 “ 有序序列 ”的过程。核心步骤1.建堆排序前的数组是完全无序的比如[4,6,8,5,9,1,3,2,7]此时无法直接快速找到最大值 或 最小值。堆的第一个作用就是将无序数组转化为 大堆 或者 小堆让数组满足 “堆顶是最大值 或 堆顶是最小值” 的特性。2.反复 “取堆顶最大值 或 最小值 修复堆”构建有序序列建堆后数组的最大值已经在堆顶但其他元素仍无序。堆的第二个作用是持续提供最大值 或 最小值并快速修复堆结构让每次都能高效取到 “剩余元素的最大值或最小值”。2.1升序建大堆为什么说升序建大堆更合理而不是建小堆更合理呢这里是很多帅观众的疑惑我们知道小堆的堆顶是堆中最小的元素对于升序而言需要每次把最小值放在数组的最前面而第一个元素已经是最小值了所以需要从第二个元素开始进行排列但我们发现以第二个元素为堆顶其堆的结构就已经破坏了需要再次对以第二个元素为堆顶进行建小堆这样每次的消耗过大所以更好的方式为建大堆请听我娓娓道来。核心思想①目标将数组排成 升序小元素在前大元素在后②堆类型大堆父节点 子节点堆顶是当前最大值③核心操作建初始大堆 → 循环交换堆顶最大值与堆尾 → 调大堆。步骤一将无序数组建成大堆。步骤二将堆顶元素与最末尾元素进行互换如图所示将堆中最大的元素9与堆尾元素1进行互换则最大元素放在了堆尾最大值 9 被固定到数组末尾最终位置后续不再处理未排序区域缩小为[1782564]。步骤三将堆尾元素1与堆顶元素交换后此时堆顶元素为1破坏了大堆的性质所以需要进行向下调整找出次大的元素放置堆顶。步骤四重复这个过程即可将无序数组排列成有序数组。代码实现#includestdio.h void Swap(int* a, int* b) { int tmp *a; *a *b; *b tmp; } void maxHeapify(int* arr, int size, int parent) { //假设左孩子节点最大 int child parent * 2 1; //进行向下调整,到根节点就退出即 childsize while ( child size ) { //假设失败右孩子大于左孩子 if (child 1 size arr[child 1] arr[child]) { child; } if (arr[child] arr[parent]) { Swap(arr[child], arr[parent]); //更新父亲节点 parent child; //更新孩子节点 child parent * 2 1; } else { break; } } } void HeapSort(int *a,int size) { //利用向下调整算法进行建堆 for (int i (size - 1 - 1) / 2; i 0; i--) { maxHeapify(a, size, i); } //end为队尾一个元素的下标 int end size - 1; //end0即为最后一个元素无需排序 while (end 0) { swap(a[0], a[end]); //交换后需要向下调整的元素个数为end maxHeapify(a, end, 0); --end; } } void testHeapSort() { int a[8] { 4 , 2 , 8 , 1 , 5 , 6 , 9 , 7 }; printf(未进行堆排之前的元素顺序\n); for (int i 0; i 8; i) { printf(%d , a[i]); } HeapSort(a, 8); printf(\n进行堆排之后的元素顺序\n); for (int i 0; i 8; i) { printf(%d , a[i]); } } int main() { testHeapSort(); return 0; }2.2降序建小堆同理若降序建小堆通过将堆顶元素与堆尾元素进行交换后然后不断进行调小堆即可让堆中的最小元素放在堆尾通过不断进行该操作即可让无序数组变成有序。核心思想①目标将数组排成 降序大元素在前小元素在后②堆类型小顶堆父节点 ≤ 子节点堆顶是当前最小值③核心操作建初始小堆 → 循环交换堆顶最小值与堆尾 → 调小堆」。步骤一将无序数组建成小堆。步骤二将堆顶元素与最末尾元素进行互换如图所示将堆中最小的元素1与堆尾元素7进行互换则最小元素放在了堆尾最小值1被固定到数组末尾最终位置后续不再处理未排序区域缩小为[7264589]。步骤三将堆顶元素1与堆尾元素交换7后此时堆顶元素为7破坏了小堆的性质所以需要进行向下调整找出次小的元素放置堆顶。步骤四重复这个过程即可将无序数组排列成有序数组。代码示例#includestdio.h void Swap(int* a, int* b) { int tmp *a; *a *b; *b tmp; } void minHeapify(int* a, int size, int parent) { //父亲节点下标parent //左孩子节点下标为parent*21 //右孩子节点下标为parent*22 //假设左孩子是最小的 int child parent * 2 1; while (child size) { if (child 1 size a[child 1] a[child] ) { child; } if (a[child] a[parent]) { //交换父亲节点和孩子节点 Swap(a[child], a[parent]); //更新父亲节点 parent child; //更新孩子节点 child parent * 2 1; } else { break; } } } void HeapSort(int *a,int size) { //利用向下调整算法进行建堆 for (int i (size - 1 - 1) / 2; i 0; i--) { minHeapify(a, size, i); } //end为队尾一个元素的下标 int end size - 1; //end0即为最后一个元素无需排序 while (end 0) { swap(a[0], a[end]); //交换后需要向下调整的元素个数为end minHeapify(a, end, 0); --end; } } void testHeapSort() { int a[8] { 4 , 2 , 8 , 1 , 5 , 6 , 9 , 7 }; printf(未进行堆排之前的元素顺序\n); for (int i 0; i 8; i) { printf(%d , a[i]); } HeapSort(a, 8); printf(\n进行堆排之后的元素顺序\n); for (int i 0; i 8; i) { printf(%d , a[i]); } } int main() { testHeapSort(); return 0; }三、复杂度分析3.1时间复杂度该算法的时间复杂度始终为O(n log n)在最好、最坏和平均情况下都保持稳定的性能表现。具体来说构建堆的过程耗时O(n)而排序阶段需要遍历n个元素每次堆调整操作的时间复杂度为O(log n)。3.2空间复杂度该算法具有O(1)的空间复杂度作为原地排序算法它无需额外的存储空间。既然看到这里了不妨关注点赞收藏感谢大家若有问题请指正。