网站代运营价格,建筑库,做基因检测网站,仕德伟做的网站上次才讲完堆的相关问题#xff1a;二叉树顺序结构与堆的概念及性质#xff08;c语言实现堆 那今天就接着来进行堆的主要两方面的应用#xff1a;堆排序和TOP-K问题 文章目录 1.堆排序1.1概念、思路及代码1.2改良代码#xff08;最初建立大堆用AdjustDow#xff09; 2. TO…上次才讲完堆的相关问题二叉树顺序结构与堆的概念及性质c语言实现堆 那今天就接着来进行堆的主要两方面的应用堆排序和TOP-K问题 文章目录 1.堆排序1.1概念、思路及代码1.2改良代码最初建立大堆用AdjustDow 2. TOP-K问题 1.堆排序
1.1概念、思路及代码 堆排序即利用堆的思想来进行排序总共分为两个步骤 建立堆 升序建立大堆降序建立小堆 利用堆删除思想来进行排序堆顶元素是当前堆中的最大值大堆或最小值小堆将堆顶元素与堆中最后一个元素交换然后将剩余元素重新调整成堆再取出堆顶元素。重复上述步骤直到所有元素都被取出即完成了排序 #define _CRT_SECURE_NO_WARNINGS 1
#includeHeap.hvoid Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}void AdjustUp(HPDataType* a, int child)
{int father (child - 1) / 2;while (child 0){if (a[child] a[father]){Swap(a[child], a[father]);//更新下标child father;father (father - 1) / 2;}else{break;//一旦符合小堆了就直接退出}}
}void AdjustDown(HPDataType* a, int n, int father)
{int child father * 2 1;//假设左孩子大while (child n){if (child 1 n a[child] a[child 1]){child;}if (a[child] a[father]){Swap(a[child], a[father]);father child;child father * 2 1;}else{break;}}
}void HeapSort(int* arr, int n)//升序
{//先建大堆for (int i 0; i n; i){AdjustUp(arr, i);}int a n - 1;while (a 0){//此时最大的是堆顶堆顶跟最后一个交换Swap(arr[0], arr[a]);//现在最大的已经在最后了不考虑它把新塔顶降下来重新编程大堆AdjustDown(arr, a, 0);a--;}}int main()
{int arr[] { 4,6,2,1,5,8,2,9 };for (int i 0; i sizeof(arr) / sizeof(int); i){printf(%d , arr[i]);}printf(\n);HeapSort(arr, sizeof(arr) / sizeof(int));for (int i 0; i sizeof(arr) / sizeof(int); i){printf(%d , arr[i]);}
}结果 1.2改良代码最初建立大堆用AdjustDow
仅仅该那一部分
void HeapSort(int* arr, int n)//升序
{//先建大堆//for (int i 0; i n; i)//{// AdjustUp(arr, i);//}for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(arr, n, i);}int a n - 1;while (a 0){//此时最大的是堆顶堆顶跟最后一个交换Swap(arr[0], arr[a]);//现在最大的已经在最后了不考虑它把新塔顶降下来重新编程大堆AdjustDown(arr, a, 0);a--;}}对于一个具有n个节点的完全二叉树来说最后一个非叶子节点的下标是(n-1-1)/2也就是说从最后一个非叶子节点开始依次向上调整每个节点就可以建立一个大堆 相比于向上调整向下调整的好处时间复杂度低
向下调整的时间复杂度是O(n)而向上调整的时间复杂度是O(nlogn)
建堆的时间复杂度为 O(n)排序过程的时间复杂度为 O(n log n)建堆的时间复杂度为 O(n)而对堆进行排序的过程中需要进行 n-1 次堆调整操作每次堆调整的时间复杂度为 O(log n)。因此排序过程的时间复杂度为 O(n log n) 2. TOP-K问题 TOP-K问题:求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大 对于Top-K问题能想到的最简单直接的方式就是排序然后直接取。 但是如果数据量非常大排序就不 太可取了最佳的方式就是用堆来解决基本思路如下 用数据集合中前K个元素来建堆 要找前k个最大的元素则建小堆要找前k个最小的元素则建大堆 用剩余的元素依次与堆顶元素来比较不满足则替换堆顶元素 要找前k个最大的元素但凡剩余的有比小堆堆顶大的就进入到堆里面然后向下沉如果建立大堆有可能一个都进不来。找前k个最小的也同理 void CreateData()//用来创建有随机数的文件的进行检测
{int N 1000;srand(time(0));FILE* f fopen(data.txt, w);for (int i 0; i N; i){int a (rand()) % 10000;fprintf(f,%d\n, a);}fclose(f);}void PrintTopK(int k)//前k个大的
{//先读文件FILE* fout fopen(data.txt, r);if (fout NULL){perror(fopen file);return -1;}int* a (int*)malloc(sizeof(int) * k);for (int i 0; i k; i)//建立元素k的小堆{fscanf(fout, %d, a[i]);//把文件里的前k个数字写入数组里AdjustUp(a, k);}//如果有比堆顶大的就进来int n 0;while (fscanf(fout, %d, n) ! EOF)//读到文件读完就停止{if (n a[0]){a[0] n;AdjustDown(a, k, 0);}}for (int i 0; i k; i){printf(%d , a[i]);}printf(\n);fclose(fout);
}int main()
{PrintTopK(5);return 0;
}结果如下 那这次堆的两大应用就先到这里啦到此二叉树顺序结构部分的知识也已经分享完毕了。感谢大家的支持希望能帮助到大家
