网站建设费走什么费用,百度邮箱登录入口,小程序定制开发哪家好,手机适配网站目录 堆的意义#xff1a;
第一是堆的排序#xff0c;第二是堆的top k 排行问题
堆的 top k 排行问题#xff1a;
面对大量数据的top k 问题#xff1a; 堆排序的实现#xff1a;——以升序为例
方法一 交换首尾#xff1a;
建立大堆#xff1a;
根结点尾结点的…目录 堆的意义
第一是堆的排序第二是堆的top k 排行问题
堆的 top k 排行问题
面对大量数据的top k 问题 堆排序的实现——以升序为例
方法一 交换首尾
建立大堆
根结点尾结点的交换配合自上而下的操作
自上而下的函数
自下而上的函数
源文件
主函数部分
方法二 反复横跳
实现
top K 排行问题— 以处理较多数据为例最大的前K个数
创建数据并存储到文件中
创建K个数的小堆 进行交换
打印堆
完整代码
自上而下调整的时间复杂度
自下而上调整的时间复杂读 堆的意义
第一是堆的排序第二是堆的top k 排行问题 堆的 top k 排行问题 堆的top k 排行问题主要是利用了 大堆或者小堆的堆顶一定是最大或者最小值的特点再利用了堆的删除操作从而进行堆的一种大小排序从而形成一种升序或者逆序的top榜单排满。 面对大量数据的top k 问题 再面对大量的数据时如果要进行排列前k个最小的数值时可以先创建一个拥有K个结点大小的小堆随后再进行插入将插入的数据和栈顶元素进行比较如果比栈顶元素小那么替换栈顶元素随后再和栈顶下的各个结点进行比较和交换。 这种做法到最后形成了一种栈顶是最小的元素的结果这种方法也相当于是一种末位淘汰制。 堆排序的实现——以升序为例
关于升序一般大多数人会想到使用小堆因为小堆的特点是父节点比子节点小而堆的底层结构又是数组所以大多数人最初想到的是使用小堆来实现堆排序问题。但这是错误的因为堆其实是一种选择排序。
如果排升序建立小堆我们可以一开始获取最小的数字但是我们下一步呢如果找第二小的数字
如果要找第二个最小的数字如果在当前这个堆的基础上找那么关系全乱了因为要在兄弟之间要在父亲的兄弟之间父亲的兄弟的孩子之间找
这时候只能重新建一个堆但是建堆的代价是时间复杂度的重复性。
所以使用大堆来解决堆排序的升序问题
方法一 交换首尾 根据堆删除的一种思想交换
根结点元素和尾结点元素的交换以大堆的父结点元素比子结点元素大的特点最后一个结点的元素是堆的最小值而根结点的元素是堆的最大值当二者进行交换后最小值跑到了根结点位置最大值跑到了最尾部结点。
而此时使用循环的方法再结合屏蔽尾部结点的方法在轮流交换的过程下很快就会形成一个以大堆的基础构建的小堆而小堆在数组中的排序便是升序的
建立大堆
使用之前构建堆的方法过于繁琐所以可以利用现成数组和自下而上的交换方法进行大堆的建立 根结点尾结点的交换配合自上而下的操作
- -end是用来屏蔽每一会的最尾结点end 是下标的意思n是数组大小的意思。 自上而下的函数 自下而上的函数 源文件 主函数部分 方法二 反复横跳
反复横跳的核心是找到最后一个结点的父节点进行自上而下的交换利用升序和大堆的特点——父结点比子结点大将父结点的元素和子结点的元素进行交换。
且每一次交换后都会形成一颗子树这时候在将这颗子树的下标跳到隔壁子树上再度进行刚才的操作这样一来左右子树的父子结构均不会被破坏且还会变成一个升序的小堆。
实现
i 表示为父结点的下标n一开始是最尾部结点的下标。 top K 排行问题— 以处理较多数据为例最大的前K个数 在之前上文堆的意义中详细讲过了堆的top k问题而这里以处理较多数据的top k 为例
创建数据并存储到文件中
这一步主要是怕数据过多导致终端卡顿 代码解读srand 函数进行选取随机然后在使用time传输随机值然后以写w的方式打开文件然后因为要产生一千万个数值而rand只能产生三万多个数字所以需要i并%上10000000之后将这些数据写入文件中fprintf最后关闭文件fin是文件的指针变量 file 是指向文件的指针fin是文件内部进行内容操作的指针 创建K个数的小堆 根据小堆的特点根部是堆中最小的数字如果需要寻找最大的数则可以通过堆顶的根结点元素进行第一道排查而比堆顶大的数则替换堆顶元素随后根据小堆的特点父结点比子结点小从而进行自上而下的交换把较大的元素丢到堆的尾部进行二次的排查。这样到最后最后一个结点是最大的数而堆顶的根结点元素则是这一千万个数种第K个最大的数。 注意这里还是使用了数组构建堆的方法而进入数组中的元素由fscanf函数从之前创建好的文件中拿取。 使用了malloc建立了一个能够存放K个元素的字节 的 空间大小作为数组。fscanf是从指定标准流中获取内容scanf是从键盘标准流中获取内容fascnf 的三个参数分别是一个文件类型的指针负责读取数据一个读取后展示的格式第三个是读数后读取的数据存放的空间fscanf读完数据后会返回EOF 进行交换
因为fscanf读完数据后会返回EOF所以 以此作为判定条件x用来寄存从文件中读取的元素当x比堆顶根结点元素大时替换堆顶根结点元素随后进行自上而下的交换进行调整堆的元素以此维持小堆结构。 打印堆
最后将堆打印 完整代码 自上而下调整的时间复杂度 自下而上调整的时间复杂读
