当前位置: 首页 > news >正文

as.net 网站开发视频教程企业全网推广公司

as.net 网站开发视频教程,企业全网推广公司,怎么拥有自己的网站,长沙做痔疮东大医院de网站上次才讲完堆的相关问题:二叉树顺序结构与堆的概念及性质(c语言实现堆 那今天就接着来进行堆的主要两方面的应用:堆排序和TOP-K问题 文章目录 1.堆排序1.1概念、思路及代码1.2改良代码(最初建立大堆用AdjustDow) 2. TO…

上次才讲完堆的相关问题:二叉树顺序结构与堆的概念及性质(c语言实现堆
那今天就接着来进行堆的主要两方面的应用:堆排序和TOP-K问题


文章目录

  • 1.堆排序
    • 1.1概念、思路及代码
    • 1.2改良代码(最初建立大堆用AdjustDow)
  • 2. TOP-K问题


1.堆排序

1.1概念、思路及代码

堆排序即利用堆的思想来进行排序,总共分为两个步骤:

  1. 建立堆
  • 升序:建立大堆
  • 降序:建立小堆
  1. 利用堆删除思想来进行排序:堆顶元素是当前堆中的最大值(大堆)或最小值(小堆),将堆顶元素与堆中最后一个元素交换,然后将剩余元素重新调整成堆,再取出堆顶元素。重复上述步骤,直到所有元素都被取出,即完成了排序
#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"void 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问题,能想到的最简单直接的方式就是排序,然后直接取。 但是:如果数据量非常大,排序就不 太可取了,最佳的方式就是用堆来解决,基本思路如下:

  1. 用数据集合中前K个元素来建堆
    • 要找前k个最大的元素,则建小堆
    • 要找前k个最小的元素,则建大堆
  1. 用剩余的元素依次与堆顶元素来比较,不满足则替换堆顶元素
    • 要找前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;
}

结果如下:

请添加图片描述


那这次堆的两大应用就先到这里啦,到此二叉树顺序结构部分的知识也已经分享完毕了。感谢大家的支持,希望能帮助到大家!!!

http://www.dt0577.cn/news/10360.html

相关文章:

  • 180天做180个网站网站怎么营销推广
  • 自助网站建设系统源码学新媒体运营最好的培训学校
  • 东营网站设计百度seo搜搜
  • 做网站合同封面哪个推广网站好
  • 网站的报价怎么做搜狗权重查询
  • 计算机网站建设论文范文seo优化入门教程
  • 郑州网站建设公司哪家专业怎么写软文推广
  • 东莞百度seo价格陕西网站seo
  • 网站建设好销售吗推56论坛
  • 著名展厅设计案例秦皇岛网站seo
  • 山西运城网站建设今日国内重大新闻
  • 东兴网站建设独立站谷歌seo
  • 三角网站建设上海好的网络推广公司
  • 找建筑类工作哪个网站好搜索引擎营销概念
  • 求一个做美食视频的网站自己如何注册网站
  • 哪个网站做logo赚钱今日最新国际新闻
  • 宜宾商城网站建设百度大搜
  • 网站制作公司商丘市查看百度关键词价格
  • 莱州网站开发怎么请专业拓客团队
  • 网站做任务包括什么谷歌外链代发
  • 公司架设网站费用怎么做分录好用搜索引擎排名
  • 京东网站开发费用营销策划方案模板
  • 网站建设项目策划书格式免费投放广告的平台
  • 宁波新亚建设公司网站百度指数什么意思
  • 黄金网站网址免费营销培训课程
  • 免费试用网站制作办公软件培训
  • 自己做的网站竞价好还是单页好关键词查询爱站网
  • 国外做ae模板网站大全seo博客优化
  • 做网站美工的前途怎么样网络公关公司
  • 网站后台首页网上推广怎么收费