什么是堆】
概念:堆是一种特殊的二叉树,具备以下两种性质
1)每个节点的值都大于(或者都小于,称为最小堆)其子节点的值
2)树是完全平衡的,并且最后一层的树叶都在最左边
这样就定义了一个最大堆。
那么下面介绍二叉堆:二叉堆是一种完全二叉树,其任意子树的左右节点(如果有的话)的键值一定比根节点大,上图其实就是一个二叉堆。
你一定发觉了,最小的一个元素就是数组第一个元素,那么二叉堆这种有序队列如何入队呢?看图:
假设要在这个二叉堆里入队一个单元,键值为2,那只需在数组末尾加入这个元素,然后尽可能把这个元素往上挪,直到挪不动,经过了这种复杂度为Ο(logn)的操作,二叉堆还是二叉堆。
那如何出队呢?也不难,看图:
出队一定是出数组的第一个元素,这么来第一个元素以前的位置就成了空位,我们需要把这个空位挪至叶子节点,然后把数组最后一个元素插入这个空位,把这个“空位”尽量往上挪。这种操作的复杂度也是Ο(logn)。
【适用范围】
海量数据前n大,并且n比较小,堆可以放入内存
【基本原理及要点】
最大堆求前n小,最小堆求前n大。方法,比如求前n小,我们比较当前元素与最大堆里的最大元素,如果它小于最大元素,则应该替换那个最大元 素。这样最后得到的n个元素就是最小的n个。适合大数据量,求前n小,n的大小比较小的情况,这样可以扫描一遍即可得到所有的前n元素,效率很高。
【扩展】
双堆,一个最大堆与一个最小堆结合,可以用来维护中位数。
【问题实例】
1)100w个数中找最大的前100个数。
用一个100个元素大小的最小堆即可。
转自:http://blog.csdn.net/hit_kongquan/article/details/6255677
相关推荐
海量数据处理相关 所谓海量数据处理,是指基于海量数据的存储、处理、和操作。正因为数据量太大,所以导致要么无 法在较短时间内迅速解决,要么无法一次性装入内存。 事实上,针对时间问题,可以采用巧妙的算法搭配...
下面的方法是我对海量数据的处理方法进行了一个一般性的总结, 当然这些方法可能并不能 完全覆盖所有的问题,但是这样的一些方法也基本可以处理绝大多数遇到的问题。 下面的一 些问题基本直接来源于公司的面试笔试题目...
大数据量,海量数据 处理方法总结 包括Bloom filter 哈希 bit-map 堆 双层桶划分 数据库索引 倒排索引 外排序 trie树等。细分为适用范围、要点、实例等。
想挑战百度、腾讯、Google,海量数据处理面试集锦,理论结合具体事例分析!
1. 给定a、b两个文件,各存放50亿个url,每个url...4. 海量日志数据,提取出某日访问百度次数最多的那个IP。(利用hash分而治之,然后上归并,堆) 5. 在2.5亿个整数中找出不重复的整数,内存不足以容纳这2.5亿个整数。
JAVA⼤数据处理题 ⼤数据处理题 1. 给定a、b两个⽂件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b⽂件共同的url? ⽅案1:可以估计每个⽂件安的⼤⼩为50G×64=320G,远远⼤于内存限制的4G。...
《海量数据库解决方案》系列丛书深受广大读者的喜爱已经长达10年之久,在被誉为“圣经”的同时,它已经变成了数据库用户不可或缺的必读书籍。作者竭力探求能够让it工作者在实际工作中轻松应用并掌控的巧妙方法,...
《海量数据库解决方案》系列丛书深受广大读者的喜爱已经长达10年之久,在被誉为“圣经”的同时,它已经变成了数据库用户不可或缺的必读书籍。作者竭力探求能够让it工作者在实际工作中轻松应用并掌控的巧妙方法,...
经过众多专家学者的努力研究,一门新兴的学科----数据挖掘技术逐步的被用于海量数据的处理。从而有效的解决了“数据爆炸却知识贫乏”的问题。而作为数据挖掘技术之一的聚类分析也越来越受到研究者的关注,它既可用于...
Mahout数据挖掘的算法库,实现常⽤数据挖掘算法(分类、聚类、回归等),调⽤接⼝,传⼊参数,减少⼯作量,针 对海量数据进⾏数据挖掘分析。Ambari⾃动化的安装部署配置管理Hadoop集群的。Zookeeper分布式协作服务,...
数据结构算法的功能实现,算法是非常重要的一门课程,包括其中的冒泡排序,快速排序,希尔排序,选择排序,堆排序,都非常重要,算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的...
德润iExcel2013将Excel文件和数据库Access、Sqlserver以及工作流的优势融合在一起,使得相距千里的不同电脑协同处理文件,完成海量数据的管理;无论是数据汇总、查询、统计,还是报表生成,均前所未有的强大和易用...
) (6)处理⼤数据常⽤排序:快速排序/堆排序/归并排序/桶排序 下⾯是⼏个例题(每个题的解法都不唯⼀,下⾯只列出了众多解法中的⼀种): 1. 给定a、b两个⽂件,各存放50亿个url,每个url各占64字节,内存限制是4G...
3)海量数据堆积 a、推模式:订阅者逻辑简单 b、拉模式:关注吞吐量,快 c、推拉结合:队列通知消费者,消费者去拉取(两次交互) d、阿里采用长连接和轮询:轮询去拉,有则拉取,无则保持长连接等待,...
大数据最核心的价值就是在于对于海量数据进行存储和分析。相比起现有的其他技术而 言,大数据的"廉价、迅速、优化"这三方面的综合成本是最优的。[6] 5意义及用途 意义 1.变革价值的力量 未来十年,决定中国是不是有...
--机器学习简单的说根据一堆已知的海量数据,利用计算机(算法)去进行演算,最终得到一个合适的计算公式(也叫机器学习模型) 来拟合这些数据的过程,就叫机器学习. 实现人脸识别的监控系统 整理来访登记监控系统主要功能:...
在中国市场,工信部发布的物联网"十二五"规划上,把信息处理技术作为4项关键技术创新工程之一提出来,其中包括了海量数据存储、数据挖掘、图像视频智能分析,这都是大数据的重要组成部分。而另外 3 项关键技术创新...
海量数据处理 bitmap Map-Reduce原理 BloomFilter原理 Trie树原理 LSM树原理 linux下操作命令以及工具 工作中常用的linux 命令 编译工具GCC 调试工具GDB 性能优化工具Perf 内存泄露检查工具Valgrind
互联网JAVA工程师进阶知识扫盲,涵盖高并发,高可用,分布,微服务,海量数据处理,金融业务等领域知识 --JAVA高级及资深技术 特别提醒!!!各个各知识点描述有插入图片辅助说明,浏览过程当中如果图片显示不出来 ...