位置: 编程技术 - 正文

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

  • 账面价值大于计税基础是什么差异
  • 个人工作室需要注册资金吗
  • 贴现的费用怎么入账
  • 成本占收入比重分析
  • 发票入不了账怎么办
  • 科技型中小企业条件
  • 跨境电子商务出来能干嘛
  • 施工企业挂靠账务处理怎么做
  • 申请生育津贴需要提供什么材料
  • 固定资产清理在财务报表哪里体现
  • 异地提供建筑服务
  • 社会团体收到的投资款怎么入账
  • 抵扣上月留抵税额的分录
  • 企业将自用设备进行出租
  • 公司进行债务重构的原因可能包括
  • 劳务费发票和建筑劳务费发票
  • 委外的加工费专用发票怎么开?
  • 顺丰的收派服务费可以抵扣吗
  • 未达起征点怎么写摘要
  • 提现的现金支票是什么
  • 工费经费用计提吗
  • 购买设备对方垫付运费会计分录
  • 销售应税产品分录
  • 无票业务如何处理
  • php统计当前在线人数
  • win7怎么更改开机启动项
  • 对公账户发放工资要固定几号打吗
  • PHP:Memcached::getResultMessage()的用法_Memcached类
  • windows11怎么操作
  • 外贸企业出口免抵退
  • 增值税检查调整科目还在用吗
  • 手把手教你暴力破解wifi密码
  • php文件上传用什么请求方法
  • 房地产企业土地使用税纳税义务终止
  • 政府购买企业服务是否交税
  • 未确认融资费用怎么算
  • 在php中使用mysql
  • thinkphp教程
  • web前端面试基础知识
  • php的time函数
  • 董事长报销应该是怎样的流程
  • 商品交换包括
  • 汇算清缴需要做账吗
  • wordpress怎么添加图片
  • 给离职员工买社保的风险
  • 自有资金等于货币资金吗
  • 工会建账需要建几本账
  • 废料处理没开票销项税
  • 应收账款多记账怎么做调整分录
  • 出差期间招待费用怎样报销
  • 兼职会计如何做账报税
  • 企业给职工发放的自产产品应作为职工福利费管理
  • 预付账款用途
  • 制造费用和生产成本影响营业利润吗
  • 会计账簿的作用之一是编报和输出会计信息
  • 私营公司预收账款怎么算
  • 本月合计结账
  • SQL Server 2005/2008 用户数据库文件默认路径和默认备份路径修改方法
  • 应该怎么消除
  • mac移动硬盘怎么改名
  • winscope是什么意思
  • winxp如何删除网卡驱动
  • centos启动卡在了启动界面
  • windows7如何设置双屏显示
  • win7无法安装怎么办
  • linux网络设备有哪些
  • win10 6个文件夹
  • Android LayoutInflater原理分析,带你一步步深入了解View(一)
  • node. js教程
  • Node.js中的全局对象有
  • listview设置item宽度
  • 详解HTTPS 的原理和 NodeJS 的实现
  • 最精简的年终工作总结
  • jquery选择父级元素
  • jQuery simpleModal插件的使用介绍
  • android_zh
  • python操作json字符串
  • 哈尔滨国税局待遇怎么样
  • 四川省地方税务局公告2018年第1号
  • 建筑企业个人所得税管理办法
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

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

    友情链接: 武汉网站建设