首页 > 其他分享 >大根堆和小根堆在海量数据的top N问题中,时间复杂度O(nlogN)

大根堆和小根堆在海量数据的top N问题中,时间复杂度O(nlogN)

时间:2023-06-22 22:13:16浏览次数:50  
标签:大根堆 Key top 根堆 关键字 heap 复杂度 2i

堆可视化操作演示:https://visualgo.net/zh/heap

堆实际上是一棵完全二叉树,其任何一非叶节点满足性质:
小根堆:Key[i]<=key[2i+1]&&Key[i]<=key[2i+2] 或者 大根堆 Key[i]>=Key[2i+1]&&key>=key[2i+2]

即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。


堆分为大根堆和小根堆:
满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大根堆(Max-heap),
满足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小根堆(Min-heap)。
由上述性质可知大根堆的堆顶的关键字肯定是所有关键字中最大的,小根堆的堆顶的关键字是所有关键字中最小的。

 

其中,大根堆和小根堆在海量数据的top N问题中,有着很好的时间复杂度。

利用小根堆解决获取大量数据中最大的N个值
利用大根堆解决获取大量数据中最小的N个值

堆调整一次的时间复杂度是O(logN)。所以,通过堆来解决top N 问题的时间复杂度是O(nlogN)
其中,n为数据的个数,N为堆维护的数据的个数。
==================

实现堆,最关键的是对元素的移动(上移/下移)。所有函数都是基于这两种操作完成的。

binary heap的定义在维基百科中, sift-up 也称为 up-heap 操作,sift-down 称为 down-heap。
sift筛选
heapq.py中,
down指的是从堆底到堆顶的过程,指的是元素的索引小了,down了。反过来,up就是堆顶到堆底的过程,索引大了,up了。
_siftdown函数:将元素向堆顶移动到符合条件为止

标签:大根堆,Key,top,根堆,关键字,heap,复杂度,2i
From: https://www.cnblogs.com/sangern/p/17498426.html

相关文章

  • Android 开发之Activity的启动模式-SingleTop
    接下来,介绍下Activity的另一种启动模式-栈顶复用模式(SingleTop)SingleTopsingleTop模式,它的表现几乎和standard模式一模一样,一个singleTopActivity的实例可以无限多,唯一的区别是如果在栈顶已经有一个相同类型的Activity实例,Intent不会再创建一个Activity,而是通过onNewIntent()被......
  • 使用 iftop 来监控流量
    我们可以用iftop来查看实时的网络流量,监控TCP/IP连接等信息。它的官方网站:http://www.ex-parrot.com/~pdw/iftop/一些常用的参数命令:查看ppp0网络接口的实时流量:#iftop-ippp0以字节(bytes)为单位显示流量(预设是位bits):#iftop-B直接显示IP,不进行DNS反解:#ifto......
  • photopea参考线
    Photopea 是一个非常实用的在线PS网站,与PS电脑软件相似度极高。包括快捷键等。地址:https://www.photopea.com/  拉辅助线的几种方法:按下CTRL+R,将标尺显示出来。从标尺处直接拉出辅助线。 执行“视图——新建参考线”,比如我们想要拉出原点开始2厘米的垂直参考线,可以按下面......
  • 8月最新-《可解释机器学习-Christoph Molnar》-新书分享
        机器学习在改进产品、过程和研究方面拥有很大的潜力。但是机器学习模型预测的结果通常是不可解释的,这也是机器学习技术最大不足。本书主要讲解如何搭建机器学习模型,并使他们的预测结果是可解释的。 (文末附本书免费下载地址)    本书首先讲解可解释性的基本概念,然后讲......
  • 54 KVM工具使用指南-vmtop使用指南
    54KVM工具使用指南-vmtop使用指南54.1概述vmtop是运行在宿主机host上的用户态工具。使用vmtop可以实时动态地查看虚拟机资源的使用情况,例如CPU占用率、内存占用率、vCPU陷入陷出次数等。因此,可以使用vmtop作为虚拟化问题定位和性能调优的工具。54.1.1多架构支持当前vmtop支......
  • Remote Desktop Manager 2023(远程桌面管理)
    RemoteDesktopManager是一款非常好用的远程桌面管理器,主要用于管理所有远程连接和虚拟机的小型应用程序。您可以快速添加、编辑、删除、共享、组织和查找远程连接,兼容微软的远程桌面或终端服务。使用起来非常简单,但同时是强大的,有效的。除了微软远程桌面,还可兼容终端服务、VNC、......
  • TensorFlow09.1 神经网络-其他训练Tricks(Early Stopping和Dropout)
    Tricks▪EarlyStopping▪Dropout▪StochasticGradientDescent1Earlystopping我们走到最大指的时候我们可以提交stop掉,防止它overfitting。1.1How-To▪Validationsettoselectparameters(选择一个参数)▪Monitorvalidationperformance(检测变量的表现)▪......
  • 【Podman Desktop】配置镜像源加速
    配置Podmandesktop镜像源加速打开阿里云https://cr.console.aliyun.com/cn-hangzhou/instances/mirrors,复制里面的加速地址打开window的Powershell,输入wsl进入linux子系统sudovi/etc/containers/registries.conf#输入命令,修改该文件添加如下内容后,使用wq保存退......
  • Windows环境下Redis的安装以及Redis Desktop Manager的下载安装
    ————本文介绍了Windows环境下Redis的安装,以及Redis数据库管理工具RedisDesktopManager的下载和安装目录|一、Windows环境下安装Redis||--|--||二、RedisDesktopManager的下载及安装|一、Windows环境下安装Redis下载地址:https://github.com/tporadowski/redis/......
  • MariaDB_installing,starting and stoping,configuring,logging in
    InstallingMariaDBBinaryTarballsvia: https://mariadb.com/kb/en/installing-mariadb-binary-tarballs/ MariaDBBinarytarballsarenamedfollowingthepattern:mariadb-VERSION-OS.tar.gz.Besureto downloadthecorrectversionforyourmachine.Note: Someb......