位置: 编程技术 - 正文

PHP利用二叉堆实现TopK-算法的方法详解(php实现二叉树)

编辑:rootadmin

推荐整理分享PHP利用二叉堆实现TopK-算法的方法详解(php实现二叉树),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:二叉堆的实现,二叉堆 数组,二叉堆排序,php实现二叉树,二叉堆 数组,php实现二叉树遍历,php实现二叉树遍历,php实现二叉树,内容如对您有帮助,希望把文章链接给更多的朋友!

前言

在以往工作或者面试的时候常会碰到一个问题,如何实现海量TopN,就是在一个非常大的结果集里面快速找到最大的前或前个数,同时要保证内存和速度的效率,我们可能第一个想法就是利用排序,然后截取前或前,而排序对于量不是特别大的时候没有任何问题,但只要量特别大是根本不可能完成这个任务的,比如在一个数组或者文本文件里有几亿个数,这样是根本无法全部读入内存的,所以利用排序解决这个问题并不是最好的,所以我们这里就用php去实现一个小顶堆来解决这个问题.

二叉堆

二叉堆是一种特殊的堆,二叉堆是完全二叉树或者是近似完全二叉树,二叉堆有两种,最大堆 和 最小堆,最大堆:父结点的键值总是大于或等于任何一个子节点的键值;最小堆:父结点的键值总是小于或等于任何一个子节点的键值

小顶堆-(图片来自网络)

二叉堆一般用数组来表示(看上图),例如,根节点在数组中的位置是0,第n个位置的子节点分别在2n+1和 2n+2,因此,第0个位置的子节点在1和2,1的子节点在3和4,以此类推,这种存储方式便於寻找父节点和子节点。

具体概念问题这里就不在多说了,如果对二叉堆有疑问的可以在好好了解下这个数据结构,下面我们就针对上述topN问题来用php代码实现并解决,为了看出区别这里先用排序的方式去实现下看下效果如何。

利用快速排序算法来实现 TopN

运行之后结果

PHP利用二叉堆实现TopK-算法的方法详解(php实现二叉树)

可以看到上面打印出了top的结果,并输出了下运行时间,大概s左右,但这只是w个数且全部能装入内存的情况,如果我们有一个文件里面有5kw或5亿个数,肯定就会有些问题了.

利用二叉堆算法来实现 TopN

实现流程是:

1、先读取个或个数到数组里面,这就是我们的topN数.

2、调用生成小顶堆函数,把这个数组生成一个小顶堆结构,这个时候堆顶一定是最小的.

3、从文件或者数组依次遍历剩余的所有数.

4、每遍历出来一个则跟堆顶的元素进行大小比较,如果小于堆顶元素则抛弃,如果大于堆顶元素则替换之.

5、跟堆顶元素替换完毕之后,在调用生成小顶堆函数继续生成小顶堆,因为需要再找出来一个最小的.

6、重复以上4~5步骤,这样当全部遍历完毕之后,我们这个小顶堆里面的就是最大的topN,因为我们的小顶堆永远都是排除最小的留下最大的,而且这个调整小顶堆速度也很快,只是相对调整下,只要保证根节点小于左右节点就可以.

7、算法复杂度的话按top最坏的情况下,就是每遍历一个数,如果跟堆顶进行替换,需要调整次的情况,也要比排序速度快,而且也不是把所有的内容全部读入内存,可以理解成就是一次线性遍历.

运行之后结果

可以看到最终的结果也是top,只不过时间只用了1s左右,而且无论是内存还是时间效率都满足我们的要求,而且跟排序比最好的一点就是不用把所有的数据集都读如到内存里面来,因为我们不需要排序,而上面是为了演示,所以直接在内存构造了w元素,然而我们可以把这个全部转移到文件里面去,然后一行一行读取进行比较,因为我们这个数据结构的核心点就是线性遍历跟内存里面很小的小顶堆结构进行比较,最终得到TopN.

总结

最后想说的就是 算法+数据结构 真的非常重要,一个好的算法可以使我们的效率大大提高。好了,

标签: php实现二叉树

本文链接地址:https://www.jiuchutong.com/biancheng/292557.html 转载请保留说明!

上一篇:mac系统下安装多个php并自由切换的方法详解(macos安装多版macos并存)

下一篇:php读取XML的常见方法实例总结(php读取文件)

  • 加油站购进成品油怎么做账
  • 什么是企业增值税和所得税
  • 暂估入账纳税调整填哪里
  • 什么情况下税务会监管
  • 企业所得税的纳税义务人不包括下列哪类企业
  • 什么是纳税义务人,在理解这一观念时应注意哪些问题
  • 委托加工物资的会计科目
  • 购货发票属于什么证据?
  • 租车开发票属于什么类
  • 小规模企业所得税优惠政策最新2023
  • 银行询证函快递怎么查
  • 企业合并固定资产增值的规定
  • 明细分类核算的方法分为
  • 代开的专用发票如何开具红字发票
  • 修理固定资产取得增值税发票能否抵扣?
  • 公司承揽员工租房个税如何入账?
  • 事业单位存货盘盈
  • 企业出口收汇核销怎么处理?
  • 增值税专用发票开错了咋办
  • 代开专用发票的数量单价单位怎么写?
  • 餐饮发票怎么进行财税处理?
  • 什么是中型企业?
  • 增值税抵扣需要哪些附件
  • 个税申报成功如何修改
  • 暂估入库借方有余额怎么处理
  • 设置bios 密码
  • 农产品进项转出的规定
  • php字符串变量
  • PHP:apache_response_headers()的用法_Apache函数
  • 红字发票只能一张一张开吗
  • php ftp上传文件
  • netsurf.exe - netsurf是什么进程 有什么用
  • 职工教育经费计入管理费用吗
  • php 访问数据库
  • thinkphp框架搭建
  • php批量上传图片到服务器
  • gpt指标
  • 企业所得税营业收入包括什么
  • 当月银行账可以下个月做吗
  • 出口退税率为0要补增值税吗
  • 处置子公司利润表
  • 当月没有发放工资是不是就不用申报个税
  • 弃置费用的现值计入固定资产
  • 房屋出租收入是其他业务收入吗
  • 用友应收系统凭证冲销后查询不到怎么办
  • 个税手续费发给财务人员 文件
  • 年末未分配利润计算公式
  • 人力资源外包服务企业
  • 分公司能
  • 软件公司购进软件会计科目
  • 增值税普票跨月作废怎么操作
  • 小微企业记账必须有会计证吗
  • 领用生产用原材料一批
  • 筹建期费用需要结转吗
  • 未开票收入怎么报税
  • 预收账款的会计编码
  • 城建税教育费附加会计分录
  • 提前支付利息如何计算
  • mysql数据查询慢
  • Red Hat Enterprise Linux AS release 4 apache+MYsql+PHP的安装和优化
  • 怎么才能给电脑提速
  • schedul2.exe - schedul2是什么进程 有什么用
  • 系统应用没有相机
  • bat批处理命令大全
  • opengl 模型视图矩阵
  • unity 角色控制器设置isTrigger问题
  • DOS命令删除文件夹
  • pygame实例
  • 请问在javascript程序中
  • unity3d应用
  • javascript函数如何定义及其作用
  • unity中如何修改prefab
  • python字典x in d
  • 云南省国家税务总局云南省电子税务局
  • 企业所得税到底是卖方承担还是买方承担
  • 南京税务登记查询官网
  • 贵州网上税务大厅官网
  • 特服号码
  • 招投标法实施条例是哪一年修正的
  • 财务会计制度及核算软件备案怎么填
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设