位置: 编程技术 - 正文

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

  • SQL注入全过程深入分析(sql注入的原理和步骤)

    直接通过Google浏览器就能去除。

    点击登录,返回的信息如下:

    Conversion failed when converting the nvarchar value 'master' to data type int.

    数据库名称“master”通过异常被显示出来!依次改变上面SQL语句中的序号,

    就能得到服务器上所有数据库的名称。

    接着,输入信息如下:

    得到返回信息如下:

    Conversion failed when converting the nvarchar value 'spt_fallback_db' to data type int.

    我们得到了master数据库中的第一张表名:“spt_fallback_db”,

    同上,依次改变序号,可得到该库全部表名。

    现在我们以“spt_fallback_db”表为例,尝试获取该表中所有的字段名。在输入框中输入以下代码:

    于是,得到错误提示如下:

    "Conversion failed when converting the nvarchar value 'xserver_name' to data type int." class="img-responsive" alt="SQL注入全过程深入分析(sql注入的原理和步骤)">

    SQL注入全过程深入分析(sql注入的原理和步骤)

  • WinXP玩LOL登录时提示Null错误的快速解决教程(xp系统玩英雄联盟出现win32)

    WinXP玩LOL登录时提示Null错误的快速解决教程(xp系统玩英雄联盟出现win32)

  • 开源操作系统是什么意思 开源操作系统简介(开源操作系统总结)

    开源操作系统是什么意思 开源操作系统简介(开源操作系统总结)

  • windows开机显示explorer.exe文件损坏且桌面上图标不见(windows开机显示正在清理)

    windows开机显示explorer.exe文件损坏且桌面上图标不见(windows开机显示正在清理)

  • Win10系统命令提示符打开方法 (win10命令提示符哪里打开)

    Win10系统命令提示符打开方法 (win10命令提示符哪里打开)

  • vi的命令(vi中的命令)

    vi的命令(vi中的命令)

  • 批处理命令详解之目录跳转:cd(批处理常用命令总结)

    批处理命令详解之目录跳转:cd(批处理常用命令总结)

  • Nodejs中Express 常用中间件 body-parser 实现解析(node.js express koa)

    Nodejs中Express 常用中间件 body-parser 实现解析(node.js express koa)

  • 会计一般什么时候考试
  • 厂部管理人员薪酬计入什么费用
  • 应收利息的概念是什么
  • 金税盘如何查看开票机号
  • 运输费计入什么科目分录
  • 纳税申报 财务报表利润表
  • 季度30万免增值税2019
  • 采购货款属于什么会计科目
  • 非正常损失会计利润调整
  • 补交以前年度增值税的科目处理
  • 其他业务利润怎么算公式
  • 涉外收入申报单填写模板
  • 未取得支付工程款的发票怎么做账?
  • 房屋出租要交产证吗
  • 自制半成品具体如何处理账务?
  • 物业服务费属于什么合同印花税
  • 国家级企业孵化器是什么意思
  • 工会经费的缴费主体
  • 企业年报资产状况信息可以不填吗
  • 企业经营者试行什么制度
  • 外币折算差额怎么记账
  • 运费发票没有开 怎么做到成本
  • 融资租赁固定资产折旧
  • 云服务器免费使用
  • 生产车间的费用会计分录
  • 产品作为样品账务处理
  • php图片拼接
  • 超市预售卡怎么记账
  • php过滤emoji
  • 支付包装物押金为什么是其他应收款
  • 如何发放年终奖 一个蒸蒸日上的公司,当
  • php获取中文字符串长度
  • 自定义修改器
  • 以下关于static
  • php时间不对
  • php的数据结构
  • html怎么做
  • 开办费对应的现金流量项目
  • 我国消费税的特点
  • 电子发票有哪些版本
  • 过年回家的你
  • 财政贴息会计处理怎么理解
  • 固定资产盘盈税务处理政策
  • 用python绘制
  • 二季度报表是累计数吗
  • 企业所得税汇算清缴表
  • 收到的普票金额多开了怎么处理呢
  • 公司银行销户钱转到哪里去
  • 天使投资
  • sql server 2008怎么用
  • mysql数据类型和索引
  • 公司向法人借款协议
  • 企业所得税的应纳税所得额怎么计算
  • 独立核算分公司与总公司的账务处理
  • 补缴社保的利息会进入个人账户里吗
  • 记账凭证会计核算形式的程序
  • 以前年度多记成本费用税前扣除,今年要怎么做分录冲销
  • 公司为员工异地缴纳五险一金
  • 实缴资本在公司能查到吗
  • 冲回以前年度工会费
  • sql 分页语句
  • sql搜索字段名
  • 如何启动vmware authorization service
  • win7旗舰版怎么进入bios
  • squid详细
  • smon进程
  • win8开始屏幕设置
  • 怎样一键清空
  • 原版windowsxp安装
  • linux系统入侵检测软件有哪些
  • unity怎么做触屏按键
  • div style display none
  • Node.js中的全局对象有
  • vue.js 2.x
  • node.js适用哪些场景
  • 批处理修改文件名称
  • javascript图片切换代码
  • 西安市电子税务局
  • 申请电子发票需要去税务局吗
  • 安徽省印花税核定
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

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

    友情链接: 武汉网站建设