top K 排行问题:— 以处理较多数据为例,最大的前K个数
堆的意义:
第一是堆的排序,第二是堆的top k 排行问题
堆的 top k 排行问题:
面对大量数据的top k 问题:
再面对大量的数据时,如果要进行排列前k个最小的数值时,可以先创建一个拥有K个结点大小的小堆,随后再进行插入,将插入的数据和栈顶元素进行比较,如果比栈顶元素小,那么替换栈顶元素,随后再和栈顶下的各个结点进行比较和交换。
堆排序的实现:——以升序为例
如果排升序建立小堆,我们可以一开始获取最小的数字,但是我们下一步呢,如果找第二小的数字?
如果要找第二个最小的数字,如果在当前这个堆的基础上找,那么关系全乱了,因为要在兄弟之间,要在父亲的兄弟之间,父亲的兄弟的孩子之间找
这时候只能重新建一个堆,但是建堆的代价是时间复杂度的重复性。
方法一 交换首尾:
根结点元素和尾结点元素的交换,以大堆的父结点元素比子结点元素大的特点,最后一个结点的元素是堆的最小值,而根结点的元素是堆的最大值,当二者进行交换后,最小值跑到了根结点位置,最大值跑到了最尾部结点。
而此时,使用循环的方法再结合屏蔽尾部结点的方法,在轮流交换的过程下,很快就会形成一个以大堆的基础构建的小堆,而小堆在数组中的排序便是升序的!
建立大堆:
使用之前构建堆的方法过于繁琐,所以可以利用现成数组和自下而上的交换方法进行大堆的建立
根结点尾结点的交换配合自上而下的操作:
– –end是用来屏蔽每一会的最尾结点,end 是下标的意思,n是数组大小的意思。
自上而下的函数 :
自下而上的函数:
源文件:
主函数部分:
方法二 反复横跳:
反复横跳的核心是找到最后一个结点的父节点,进行自上而下的交换,利用升序和大堆的特点——父结点比子结点大,将父结点的元素和子结点的元素进行交换。
实现:
top K 排行问题:— 以处理较多数据为例,最大的前K个数
在之前上文堆的意义中,详细讲过了堆的top k问题,而这里以处理较多数据的top k 为例
创建数据并存储到文件中:
- 代码解读:
- srand 函数进行选取随机,然后在使用time传输随机值,然后以写(”w”)的方式打开文件
- 然后因为要产生一千万个数值,而rand只能产生三万多个数字所以需要+i并%上10000000
- 之后将这些数据写入文件中(fprintf),最后关闭文件,fin是文件的指针变量
创建K个数的小堆:
- 根据小堆的特点,根部是堆中最小的数字,如果需要寻找最大的数,则可以通过堆顶的根结点元素进行第一道排查
- 而比堆顶大的数则替换堆顶元素,随后根据小堆的特点,父结点比子结点小,从而进行自上而下的交换,把较大的元素丢到堆的尾部进行二次的排查。
- 这样到最后,最后一个结点是最大的数,而堆顶的根结点元素则是这一千万个数种第K个最大的数。
进行交换:
因为fscanf读完数据后会返回EOF,所以 以此作为判定条件,x用来寄存从文件中读取的元素,当x比堆顶根结点元素大时,替换堆顶根结点元素,随后进行自上而下的交换进行调整堆的元素,以此维持小堆结构。
打印堆:
完整代码:
自上而下调整的时间复杂度:
自下而上调整的时间复杂读:
原文地址:https://blog.csdn.net/2301_76445610/article/details/134699288
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_36320.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!