网站改版 百度影响,如何在服务器上放网站,wordpress商务版,广州网站建设 骏域网站建设专家引言
上篇博客讲到了堆是什么#xff0c;以及堆的基本创建和实现#xff0c;这次我们再来对堆这个数据结构更进一步的深入#xff0c;将讲到的内容包括#xff1a;向下调整建堆#xff0c;建堆的复杂度计算#xff0c;堆排序和topk问题。话不多说#xff0c;开启我们今…引言
上篇博客讲到了堆是什么以及堆的基本创建和实现这次我们再来对堆这个数据结构更进一步的深入将讲到的内容包括向下调整建堆建堆的复杂度计算堆排序和topk问题。话不多说开启我们今天的内容吧。
堆排序
在讲堆排序之前我想讲讲建堆的问题。在上篇博客中我们建堆的时候是存在一个数组数组中存储着我们建堆所需要的元素通过一个个取出数组中的元素并插入新的堆中达到建堆目的。这时我们可以想如果需要直接在存储元素的数组上建堆应该怎么处理呢
向上调整建堆
如果你学会了向上调整你应该不难想到可以这样写
//这里是在原数组的基础上建立大堆
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}void AdjustUp(int* a, int child)
{int parent (child - 1) / 2;while (child 0) {if (a[parent] a[child]) {Swap(a[parent], a[child]);child parent;parent (child - 1) / 2;}else break;}
}int main()
{int arr[] { 6,5,4,3,2,1,8,7,5,4,2 };for (int i 0; i sizeof(arr) / sizeof(arr[0]); i) {AdjustUp(arr, i);}for (int i 0; i sizeof(arr) / sizeof(arr[0]); i) {printf(%d , arr[i]);}return 0;
}
上面的代码即对堆中每一个元素经行向上调整最后我们就能成功的得到一个大堆 向下调整建堆
其实有一种比向上调整建堆时间复杂度更优的方式那就是向下调整建堆这里要注意的一点就是向下调整的使用条件根节点的左右子树都得是堆。数组中的元素开始是无序的想要向下调整建堆就需要从下往上建。由于二叉树最后一层不需要向下调整所以我们可以直接从倒数第二层开始向下调。倒数第二层的末尾元素就是size - 1 - 1/ 2
代码实现向下调整建堆就是这样
//这里是在原数组的基础上建立大堆
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}void AdjustDown(int* a, int n, int parent)
{int child parent * 2 1;while (child n) {if (child 1 n a[child 1] a[child])child;if (a[child] a[parent]) {Swap(a[child], a[parent]);parent child;child parent * 2 1;}else break;}
}int main()
{int arr[] { 6,5,4,3,2,1,8,7,5,4,2 };int size sizeof(arr) / sizeof(arr[0]);for (int i (size-1-1)/2; i 0; i--) {AdjustDown(arr, size, i);}for (int i 0; i sizeof(arr) / sizeof(arr[0]); i) {printf(%d , arr[i]);}return 0;
}
打印结果和向上调整建堆相同 图解分析此过程 时间复杂度分析
为什么说向下调整建堆的复杂度更低呢这确实可以用正规的方式来推一下证明这不是凭空想象出来的结论。
堆是完全二叉树满二叉树也是完全二叉树此处为了简化用直接满二叉树来计算建堆的复杂度这里实际上多几个结点并不影响时间复杂度实际计算中计算的也只是一个近似值
1.向上调整时间复杂度计算
需要移动结点的总步数为
F(h) 2^0 * 0 2^1 * 1 2^2 * 2 …… 2^(h-1) * (h - 1)
会发现这是一个等差乘等比的差比数列前n项之和大家高中应该学过错位相减吧这里我们用错位相减求和就可以。
1式 2 * F(h) 2^1 * 0 2^2 * 1 2^3 * 2 …… 2^h * (h - 1)
2式F(h) 2^0 * 0 2^1 * 1 2^2 * 2 …… 2^(h-1) * (h - 1)
1式 - 2式
F(h) -2^1 - 2^2 - 2^3 -……-2^(h-1) 2^h * (h - 1)
上式的加粗部分是一个等比数列运用等比数列求和公式即可得 F(h) 2^h * (h - 2) 2 而我们又可以导出节点数N和树的深度h之间的关系 N 2^h-1 --- h log(N1) 带入F(h)中可得 F(N) (N1)*[ log(N1)-2 ] 2 时间复杂度即为O(N*logN) 2.向下调整时间复杂度的计算 则需要移动的步数为
F(h) 2^0 * (h-1) 2^1 * (h-2) …… 2^(h-3) * 2 2^(h-2) * 1
这里也是一个差比数列列两个式子 1式F(h) 2^0 * (h-1) 2^1 * (h-2) …… 2^(h-3) * 2 2^(h-2) * 1
2式2 * F(h) 2^1 * (h-1) 2^2 * (h-2) …… 2^(h-2) * 2 2^(h-1) * 1
1式 - 2式
F(h) 1 - h 2^1 2^2 2^3 2^4 …… 2^(h-2) 2^(h-1)
等比数列公式一套一化简 F(h) 2^h - 1 - h 我们已知N和h之间的关系N 2^h-1 --- h log(N1)
最终可得 F(N) N -log(N1) 时间复杂度即为O(N) 算到这里就可以非常轻松的比较出两个方式建堆复杂度的优劣了向下调整建堆更优。
堆排序的实现
先放上堆排序代码再来进行讲解
//堆排序
//交换两个变量
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}
//向下调整
void AdjustDown(int* a, int n, int parent)
{int child parent * 2 1;while (child n) {if (child 1 n 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 n)
{//向下调整建堆for (int i (n - 1 - 1) / 2; i 0; i--) {AdjustDown(a, n, i);}//每次选出一个最大值int end n - 1;while (end 0) {Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}
//使用堆排序
int main()
{int arr[] { 6,5,4,3,2,1,8,7,5,4,2 };for (int i 0; i sizeof(arr) / sizeof(arr[0]); i) {printf(%d , arr[i]);}printf(\n);HeapSort(arr, sizeof(arr) / sizeof(arr[0]));for (int i 0; i sizeof(arr) / sizeof(arr[0]); i) {printf(%d , arr[i]);}printf(\n);return 0;
} 可以运行一下看看结果 你可能会问代码中建立的是大堆是怎么排出了由小到大的效果呢其实这个过程和堆的删除过程是及其相似的
堆顶存储的是整个堆中最大的元素当与堆末尾的元素交换之后最大的元素就成功放到数组的末尾通过向下调整之后堆顶存放的便是堆中第二大的元素每次交换堆底都减1排好的元素不再参与向下调整的过程这时堆底新的堆底和堆顶再次交换回到步骤1
堆排序的过程其实就是这样图解 这里再次总结堆排序即利用堆的思想来进行排序总共分为两个步骤 1. 建堆 * 升序建大堆 * 降序建小堆 2. 利用删除思想来进行排序 TOP-K问题
TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。
比如几十个几百个几千个甚至上亿个数字中找到最大的前K个数字。
对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(你甚至无法将数据放入数组)。最佳的方式就是用堆来解决基本思路如下 1. 用数据集合中前k个来建堆 * 要找最大的前k个元素建小堆 * 要找最小的前k个元素建大堆 2. 用剩余的N - K个元素依次与栈顶元素来比较不满足则替换堆顶元素向下调整 将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素本topk示例代码中计算的是最大的前K个。
在这里我们可以用文件操作的方式来试一试我们先来写一个造数据的函数。
void CreateNDate()
{// 造数据int n 10000;srand(time(0));const char* file data.txt;FILE* fin fopen(file, w);if (fin NULL){perror(fopen error);return;}for (size_t i 0; i n; i){int x rand() % 1000000;fprintf(fin, %d\n, x);}fclose(fin);
}
这里将造出来的数据写入到 data.txt 文件中运行完此函数后当前目录下会多一个data.txt文件 打开此文本文件 通过此函数我们已经成功造出了10000个数据了
接下来就是topk代码的实现
#includetime.h
#includestdio.h
#includestdlib.h//交换函数
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}//向下调整
void AdjustDown(int* a, int n, int parent)
{int child parent * 2 1;while (child n) {if (child 1 n a[child 1] a[child])child;if (a[child] a[parent]) {Swap(a[child], a[parent]);parent child;child parent * 2 1;}else break;}
}//topk代码
void PrintTopK(int k) //这里的k是选出最大的前k个数
{//打开需要查找前K大数据的文件---data.txtFILE* file fopen(data.txt, r);if (file NULL) {perror(fopen fail:);exit(1);}//创建存放堆数据的空间int* arr (int*)malloc(sizeof(int) * (k 1));if (arr NULL) {perror(malloc fail:);exit(1);}//输入文件中前k个数据for (int i 0; i k; i) {fscanf(file, %d, arr[i]);}//将放入的前k个数字调整建堆for (int i (k - 1 - 1) / 2; i 0; i--) {AdjustDown(arr, k, i);}//这里是topk的重点遍历K - N的数字将符合的数字插入堆中for (int i k; i 10000; i) {int tmp 0;fscanf(file, %d, tmp);//如果tmp比堆顶的数据大则放入堆顶向下调整if (tmp arr[0]) {arr[0] tmp;AdjustDown(arr, k, 0);}}//打印前K个最大的数字for (int i 0; i k; i) {printf(%d , arr[i]);}
}int main()
{//输入选前多少大数字int digit 10;scanf(%d, digit);PrintTopK(digit);return 0;
} 这里程序成功选出了文件中前100大的数字如果觉得这样不够严谨你也可以添加几个位数较高的数据到文件中看看你的程序能否选出你写入文件的几个特殊的大数字即可。相信在这些测试过后你可以成功感受到topk算法的魅力。
结语
到这里基本上就是二叉树顺序结构堆的全部内容了本篇博客带大家学习了解了堆排序计算了向上调整建堆向下调整建堆的时间复杂度最后还说到了topk算法。这些内容其实并不难只要肯下功夫肯动手一定能学下来。后面博主还会带大家了解关于二叉树链式结构的内容欢迎大家多多关注和支持我比心-♥
