位置: 编程技术 - 正文

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

  • 报税扣款锁定如何解除
  • 受让应收账款的账务处理
  • 预付账款和应付账款的区别
  • 用友T3资产负债表公式
  • 法人其他应付款在借方表示
  • 职工的补助金需交税吗
  • 出售无形资产和转让无形资产
  • 一揽子交易定义
  • 一般纳税企业可以变更小微企业吗
  • 核定和查账区别
  • 生产设备购买交付会计分录
  • 项目现金流量的构成
  • 不动产在建工程使用的外购货物
  • 没有单价数量只有金额的发票可以用吗
  • 增值税需要自己交吗
  • 代扣款怎么做账
  • 税务稽查补缴的税款需要申报吗
  • 是否有综合所得申报是什么意思
  • 固定资产投资方案
  • 城市维护建设税的计税依据是什么
  • 污水处理增值税征收品目
  • 五月份开的发票但是七月冲红了七月增值税怎么报
  • 临时设施需要验收吗
  • 建筑劳务预缴税款后怎么申报
  • SQL Server2005、2008如何彻底删除卸载并重新安装?
  • 物业公司营业成本包括哪些
  • 手机测wifi网速准不准
  • 怎么更新电脑系统win10
  • 差额增值税发票和全额增值税发票
  • 商场充值卡发票在哪开
  • 公司为员工发放生日福利
  • 营改增后土增税收入
  • 现金长款怎么做会计分录
  • 商品销售税金及附加包括哪些
  • framework core
  • 应交消费税涉及哪些情况
  • 全网最新的暗号
  • web后端开发是什么意思
  • configure命令
  • js原型模式创建对象的优缺点
  • 资产基金的明细科目
  • 出售无形资产净收益计入什么科目
  • 公司项目支付的钱叫什么
  • 织梦cms要钱吗
  • mongo --eval
  • 勾选了不抵扣还能抵扣
  • mysql关闭连接命令
  • 财务费用 科目
  • 对公账户收钱要手续费吗
  • 贷款担保费应计入什么
  • 建筑发票开具与土增税扣有什么关系?
  • 定额转查账征收
  • 投资折价会计处理
  • 如何计算债券实际收益
  • 赠送货物金额为多少
  • 简易计税项目可以抵扣进项税吗?
  • 企业会计准则和小企业准则的区别
  • 企业共同控制持股比例怎么算
  • 业务招待费管理草案探讨
  • 会计交接事项有哪些
  • winxp cmd
  • mysql数据库性能监控
  • 上网本安装win7
  • linux acl设置
  • 开启win10
  • 如何解决win7系统卡顿
  • cmd运行指令闪黑框
  • python伪装请求头
  • linux归档文件什么意思
  • Android OpenGL ES(九)----构建几何物体
  • 安卓数据网络
  • javascript 日期
  • js的调用函数
  • 表单中的单选框
  • Android调整按钮位置
  • 税务系统会议费管理办法
  • 打印个人住房信息查询记录需要什么资料
  • 国家税务总局安徽省税务局公告
  • 公司迁税务所流程
  • 市中区税务局办税大厅上班时间
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

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

    友情链接: 武汉网站建设