位置: 编程技术 - 正文

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读取文件)

  • 金税盘抵减增值税的账务处理
  • 增值税16%降到13%的留抵退税的情况说明咋写
  • 营业净利率和总资产净利率的区别
  • 印花税是根据什么征收的
  • 新企业需要结转增值税吗
  • 地下建筑房产税减免优惠政策
  • 工程未竣工如何结算
  • 我公司开给对方13个点发票,后期我公司怎么抵税
  • 内账和外账会计哪个简单
  • 企业为什么要缴纳增值税
  • 个体户怎么申请核定征收
  • 房地产开发公司注册资金要求
  • 购买方开具红字信息表
  • 总账每个月都要结账吗
  • 固定资产改扩建过程中,发生的人工费用
  • macbook怎么修改默认系统
  • 代发工资如何合理避税
  • 应付股利属于什么科目
  • windows商店下载不了
  • 计提税金及附加的金额如何算
  • 进项发票认证后多久可以申报
  • 增值税的特殊项目
  • php5 mysql教程
  • 同一控制下控股合并在合并日合并报表编报正确的有
  • php批量处理数据
  • php编辑器哪个好
  • vue创建项目后开始写的步骤
  • vscode+cmake
  • ghostnet改进
  • redis常见问题解决
  • 专利收费的职能包括
  • 货款收不回来会计分录
  • 垃圾清运费进入会计什么科目
  • 委托境外机构销售开发产品
  • 缴税的会计处理
  • 年底应交增值税借方余额怎么处理
  • 停车费报销怎么说委婉
  • 出纳对现金的收付应该怎么做
  • mdf和ndf文件
  • 内账中采购另付的税点算成本还是费用
  • 企业开外币户有什么用
  • 固定资产办理竣工结算之后的处理方式
  • 特殊收入如何计税
  • 消费税计税分录
  • 建筑业增值税税负率
  • 商标权的入账价值有哪些
  • 企业退休返聘人员怎么规避风险
  • 私车公用税务处理
  • 固定资产能直接计入费用吗为什么
  • 离岸服务外包收入
  • 发票怎么保管不会坏
  • 收到银行结息收入怎么做会计分录
  • 试制流程
  • mac查找序列号
  • 懒癌患者如何自救
  • win10预览版绿屏重启解决
  • windows10怎么隐藏工具栏
  • FreeBSD中使用QUOTA(磁盘配额)来限制用户空间
  • G40/50-70、SR1000随机Linux改安装Win7系统的实现方法
  • win10预览版21h2
  • xp系统进入桌面后没反应
  • 微软被告
  • win7如何获取管理员密码
  • 如何制作u盘启动盘
  • javascript怎么做
  • js 对象内存 占用
  • 创建步骤
  • angular form表单
  • js null,undefined,字符串小结
  • Jar mismatch! Fix your dependencies
  • jquery轮播图代码
  • java教程
  • js register
  • 安徽省国家税务局通用定额发票
  • 北京税务局几点下班?
  • 地方税务局网上申报
  • 厦门增值税发票查验
  • 契税个税怎么说
  • 地方税务局投诉有用吗
  • 电子发票查询官网入口国家税务局重庆电子税务
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

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

    友情链接: 武汉网站建设