【数据结构】(堆)Top-k|堆排序

目录

概念:

堆的实现 

构建

初始化

销毁

插入元素

往上调整 

删除堆顶元素 

往下调整 

返回堆顶元素 

 返回有效个数

是否为空

 堆排序

 Top-k问题

​编辑 创建数据

堆top-k


概念:

堆是将数据按照完全二叉树存储方式存储到一维数组中;

堆分为大堆和小堆:

大堆:父结点大于等于孩子结点;

小堆:父结点小于等于孩子结点;

父结点与(左右)孩子结点关系:

1.父结点 = (孩子结点-1)/2;

2.左结点= (父结点*2)+1;

        右结点= (父结点*2)+2;

堆的实现 

堆的逻辑结构是完全二叉树,物理结构是一维数组存储;

而独特的结点关系,堆排序也是一种选择排序,

构建

typedef int HPDataType;
typedef struct Heap
{HPDataType* parr;int size;		//存储的有效数据个数int capacity;	//容量
}Heap;
//	用数组存储    

初始化

//堆的初始化
void HeapInit(Heap* php)
{assert(php);php->parr = NULL;php->size = 0;php->capacity = 0;
}

销毁


//堆的销毁
void HeapDestroy(Heap* php)
{assert(php);free(php->parr);php->parr = NULL;php->size = php->capacity = 0;free(php);php = NULL;
}

插入元素

因为堆分为两类,在数据插入时,需要选择适应的调整;

以小堆来说:当插入一个新元素时,插入到堆尾,与父结点比较,相应的往上调整

//堆的插入元素
void HeapPush(Heap* php, HPDataType x)
{assert(php);//检查容量if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* newparr = (HPDataType*)realloc(php->parr, sizeof(HPDataType) * newcapacity);if (newparr == NULL){perror("realloc fail");exit(-1);}php->capacity = newcapacity;php->parr = newparr;}php->parr[php->size] = x;php->size++;//小堆//向上调整AdjustUp(php->parr, php->size - 1);
}

往上调整 

当插入一个新元素,按照孩子和父结点之间的关系进行比较,交换两结点数据,直到满足堆的性质 

//向上调整
void AdjustUp(HPDataType* parr,int size)
{int child = size;int parent = (child - 1) / 2;//小堆=> 父结点<=孩子结点while (child>0){if (parr[child] < parr[parent]){//交换数据Swap(&parr[child], &parr[parent]);child = parent;        //更新结点位置parent = (child - 1) / 2;}else{break;}}
}

删除堆顶元素 

1.将堆顶元素和尾部元素互换位置;

2.将此刻不符合规定的堆顶元素往下调整至相应位置; 

// 删除堆顶(根节点)
void HeapPop(Heap* php)
{assert(php);//1.堆顶元素和尾部元素置换位置Swap(&php->parr[0], &php->parr[php->size - 1]);php->size--;	//删掉交换后的堆顶元素//2.将新站顶元素找到相应位置//向下调整AdjustDown(php->parr,php->size,0);
}

往下调整 

堆顶元素与其孩子结点比较,如何找到较大(较小)的孩子?

可以假设法:假设较大(较小)的孩子为左孩子,然后验证假设;

//向下调整
void AdjustDown(HPDataType* parr,int size,int parent)
{int child = (parent * 2) + 1;while (child<size)	//{//假设左孩子为较小值if (child+1<size && parr[child + 1] < parr[child])	//验证假设{++child;	//说明右孩子更小,更换孩子位置}//检查是否不符合堆排序结构 if (parr[parent] > parr[child]){Swap(&parr[parent], &parr[child]);//往下更新父结点 孩子结点位置parent = child;child = parent * 2 + 1;}else{break;}}
}

返回堆顶元素 

起始值为0;

//返回堆顶元素
HPDataType HeapTop(Heap* php)
{assert(php);assert(php->size > 0);return php->parr[0];
}

 返回有效个数

注意,构建堆的时候,size是最后一个元素的下一个;

//返回堆内有效数据个数
size_t HeapSize(Heap* php)
{assert(php);return php->size;	//数组下标0开始
}

是否为空

//判断堆是否为空
bool HeapEmpty(Heap* php)
{return php->size == 0;
}

 堆排序

以上是一些堆的简单功能实现;算不上真正的堆排序;

假设给定一串数字,4,6,2,1,5,8,2,9;如何将其排序?比如升序;

  1. 建立一个大堆;
  2. 将堆顶元素与堆尾元素互换,且将遍历堆的范围-1,保证其想要的值保持不动;
  3. 将此刻不符合规定的堆顶往下调整,找到次大的值;重复步骤2;

其实相当于第一个元素默认是堆,后面的进行遍历调整; 

//排序,升序
void HeapSort(int* parr, int n)
{//1.建立大堆for (int i = 1;i < n; i++){justUp(parr, i);}//2.堆顶元素与堆尾元素互换,然后将堆size-1(指只需要遍历到的位置)int end = n - 1;while (end>0){//堆顶和堆尾 元素呼唤Swap(&parr[0], &parr[end]);//往下调整justDown(parr,end,0);end--;}
}

也有其他思路;

我们从下面子树往上遍历,而内部调整时往下调整

 n-1是最后结点下标值,(结点-1)/2 可以得到该结点的父结点,从父结点往下调整;

for (int i = (n-1-1)/2; i >= 0; --i){AdjustDown(parr, n, i);}

 Top-k问题

在排序的基础上,如果这个数很大呢,比如一百万个数,要找到前k个较大值;

此刻建堆排序显然不合适;

1.读取前K个值,建立其小堆;

2.依次读取后面的值,与堆顶比较:如果比堆顶大,替换堆顶进堆,再往下调整;

 创建数据

//tok-k 问题
//创建一千万的数据
void CreateNode()
{// 造数据int n = 10000000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (int i = 0; i < n; ++i){int x = (rand() + i) % 10000000;	//+i是 因为随机数产生只有三万个,加上i可以大大减少重复值fprintf(fin, "%d\n", x);}fclose(fin);
}

堆top-k

开辟K个数的空间(动态数组);

建立K个数的小堆;

读取文件中值,遍历与堆顶比较,

void HeapTok(const char* file,int k)
{FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}//开辟K个数的空间int* minheap = (int*)malloc(sizeof(int) * k);if (minheap == NULL){perror("malloc error");return;}//建立K个数的小堆for (int i = 0; i < k; i++){//从文件流中 读取数据存到 开辟的空间中fscanf(fout,"%d", &minheap[i]);//往上调整AdjustUp(minheap, i);}//遍历文件数据 int x = 0;while (fscanf(fout, "%d", &x) != EOF)	{if (x > minheap[0]){minheap[0] = x;//往下调AdjustDown(minheap, k, 0);}}//打印tokfor (int i = 0; i < k; i++){printf("%d ", minheap[i]);}free(minheap);fclose(fout);
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/220728.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Python】—— 如果使用matplotlib做数据可视化

matplotlib做数据可视化 相关知识掌握matplotlib的基本使用方法1. 折线图2. 散点图3. 柱状图4. 饼图5. 直方图6. 等高线图7. 图形定制 掌握数据处理的基本方法1. 数据筛选2. 缺失值处理3. 异常值处理 理解数据可视化的原则和方法1. 选择合适的图表类型2. 避免数据混淆3. 突出重…

金智融门户(统一身份认证)同步数据至钉钉通讯录

前言:因全面使用金智融门户和数据资产平台,二十几个信息系统已实现统一身份认证和数据同步,目前单位使用的钉钉尚未同步组织机构和用户信息,职工入职、离职、调岗时都需要手工在钉钉后台操作,一是操作繁琐,二是钉钉通讯录更新不及时或经常遗漏,带来管理问题。通过金智融…

.NET 自定义中间件 判断是否存在 AllowAnonymousAttribute 特性 来判断是否需要身份验证

public Task InvokeAsync(HttpContext context){// 获取终点路由特性var endpointFeature context.Features.Get<IEndpointFeature>();// 获取是否定义了特性var attribute endpointFeature?.Endpoint?.Metadata?.GetMetadata<AllowAnonymousAttribute>();if …

修复泰坦陨落2缺少msvcr120.dll的5种方法,亲测有效

游戏《泰坦陨落2》缺少msvcr120.dll的问题困扰着许多玩家。这个问题的主要原因可能是系统环境不完整、软件或游戏版本不匹配、DLL文件丢失或损坏以及杀毒软件误判等。msvcr120.dll是Microsoft Visual C 2013 Redistributable的一个组件&#xff0c;它包含了许多运行库文件&…

LeetCode 142. 环形链表 II

给定一个链表的头节点 head &#xff0c;返回链表开始入环的第一个节点。 如果链表无环&#xff0c;则返回 null。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;则链表中存在环。 为了表示给定链表中的环&#xff0c;评测系统内部使用整…

运维实践|采集MySQL数据出现many connection errors

文章目录 问题出现问题分析当前环境问题分析 解决方案1 检查调度事件任务是否开启2 开启调度事件任务3 创建一张日志表4 创建函数存储过程5 创建事件定时器6 开启事件调度任务7 检查核实是否创建 总结 问题出现 最近在做OGG结构化数据采集工作&#xff0c;在数据采集过程中&am…

【微服务】Spring Aop原理深入解析

目录 一、前言 二、aop概述 2.1 什么是AOP 2.2 AOP中的一些概念 2.2.1 aop通知类型 2.3 AOP实现原理 2.3.1 aop中的代理实现 2.4 静态代理与动态代理 2.4.1 静态代理实现 三、 jdk动态代理与cglib代理 3.1 jdk动态代理 3.1.1 jdk代理示例 3.1.2 jdk动态代理模拟实现…

用23种设计模式打造一个cocos creator的游戏框架----(二十)解析器模式

1、模式标准 模式名称&#xff1a;解析器模式 模式分类&#xff1a;行为型 模式意图&#xff1a;给定一个语言&#xff0c;定义它的文法的一种表示&#xff0c;并定义一个解释器&#xff0c;这个解释器使用该表示来解释语言中的句子。 结构图&#xff1a; 适用于&#xff1…

TikTok矩阵玩法分享,如何建立TikTok矩阵?

矩阵是在 TikTok 上非常常见的营销方式&#xff0c;很多卖家想要通过矩阵化运营快速涨粉。但要想做好TikTok矩阵&#xff0c;需要有明确的方向和计划。下面东哥我将分享一些做TikTok矩阵的玩法&#xff0c;帮助大家更好地搭建自己的TikTok矩阵。 了解TikTok矩阵 TikTok矩阵是一…

Qt 数据库QSqlDatabase使用记录

记录一些在QT中使用QSqlDatabase操作数据库时&#xff0c;需要注意的地方 创建数据库 bool CDBOperatorAbstract::_openDBConn(CDatabaseConfig config) {QWriteLocker locker(&m_locker);QSqlDatabase db;if(QSqlDatabase::contains(m_connectionName)){db QSqlDatabas…

微信小程序校园跑腿系统怎么做,如何做,要做多久

​ 在这个互联网快速发展、信息爆炸的时代&#xff0c;人人都离不开手机&#xff0c;每个人都忙于各种各样的事情&#xff0c;大学生也一样&#xff0c;有忙于学习&#xff0c;忙于考研&#xff0c;忙着赚学分&#xff0c;忙于参加社团&#xff0c;当然也有忙于打游戏的&#x…

数据可视化---饼图、环形图、雷达图

类别内容导航机器学习机器学习算法应用场景与评价指标机器学习算法—分类机器学习算法—回归机器学习算法—聚类机器学习算法—异常检测机器学习算法—时间序列数据可视化数据可视化—折线图数据可视化—箱线图数据可视化—柱状图数据可视化—饼图、环形图、雷达图统计学检验箱…

PDF转为图片

PDF转为图片 背景pdf展示目标效果 发展过程最终解决方案&#xff1a;python PDF转图片pdf2image注意&#xff1a;poppler 安装 背景 最近接了一项目&#xff0c;主要的需求就是本地的文联单位&#xff0c;需要做一个电子刊物阅览的网站&#xff0c;将民族的刊物发布到网站上供…

LVS简介及LVS-NAT负载均衡群集的搭建

目录 LVS群集简介 群集的含义和应用场景 性能扩展方式 群集的分类 负载均衡&#xff08;LB&#xff09; 高可用&#xff08;HA&#xff09; 高性能运算&#xff08;HPC&#xff09; LVS的三种工作模式 NAT 地址转换 TUN IP隧道 IP Tunnel DR 直接路由 Direct Rout…

Xpath注入

这里学习一下xpath注入 xpath其实是前端匹配树的内容 爬虫用的挺多的 XPATH注入学习 - 先知社区 查询简单xpath注入 index.php <?php if(file_exists(t3stt3st.xml)) { $xml simplexml_load_file(t3stt3st.xml); $user$_GET[user]; $query"user/username[name&q…

SLAM学习——相机模型(针孔+鱼眼)

针孔相机模型 针孔相机模型是很常用&#xff0c;而且有效的模型&#xff0c;它描述了一束光线通过针孔之后&#xff0c;在针孔背面投影成像的关系&#xff0c;基于针孔的投影过程可以通过针孔和畸变两个模型来描述。 模型中有四个坐标系&#xff0c;分别为world&#xff0c;c…

机器学习 | SVM支持向量机

欲穷千里目&#xff0c;更上一层楼。 一个空间的混乱在更高维度的空间往往意味着秩序。 Machine-Learning: 《机器学习必修课&#xff1a;经典算法与Python实战》配套代码 - Gitee.com 1、核心思想及原理 针对线性模型中分类两类点的直线如何确定。这是一个ill-posed problem。…

Unity中URP下的菲涅尔效果实现(个性化修改)

文章目录 前言一、我们修正一下上篇文章中&#xff0c;可能遗留的Bug1、N向量 变为 单位向量2、使颜色范围在合理区间 二、实现菲涅尔效果强弱可自定义调节三、修改菲涅尔效果颜色1、在属性面板定义颜色属性2、在常量缓冲区申明该参数3、在片元着色器中&#xff0c;用颜色和菲涅…

使用 React 实现自定义数据展示日历组件

目录 背景实现日历组件父组件数据 效果最后 背景 项目中需要实现一个日历组件&#xff0c;并且需要展示月&#xff0c;日所对应的数据&#xff08;因为项目需求问题&#xff0c;就不统计年数据总量&#xff09;。网上找了一堆&#xff0c;基本都不大符合项目需求&#xff0c;且…

Java 基础学习(十一)File类与I/O操作

1 File类 1.1 File类概述 1.1.1 什么是File类 File是java.io包下作为文件和目录的类。File类定义了一些与平台无关的方法来操作文件&#xff0c;通过调用File类中的方法可以得到文件和目录的描述信息&#xff0c;包括名称、所在路径、读写性和长度等&#xff0c;还可以对文件…