【什么是堆】
概念:堆是一种特殊的二叉树,具备以下两种性质
1)每个节点的值都大于(或者都小于,称为最小堆)其子节点的值
2)树是完全平衡的,并且最后一层的树叶都在最左边
这样就定义了一个最大堆。如下图用一个数组来表示堆:
那么下面介绍二叉堆:二叉堆是一种完全二叉树,其任意子树的左右节点(如果有的话)的键值一定比根节点大,上图其实就是一个二叉堆。
你一定发觉了,最小的一个元素就是数组第一个元素,那么二叉堆这种有序队列如何入队呢?看图:
假设要在这个二叉堆里入队一个单元,键值为2,那只需在数组末尾加入这个元素,然后尽可能把这个元素往上挪,直到挪不动,经过了这种复杂度为Ο(logn)的操作,二叉堆还是二叉堆。
那如何出队呢?也不难,看图:
出队一定是出数组的第一个元素,这么来第一个元素以前的位置就成了空位,我们需要把这个空位挪至叶子节点,然后把数组最后一个元素插入这个空位,把这个“空位”尽量往上挪。这种操作的复杂度也是Ο(logn)。
【适用范围】
海量数据前n大,并且n比较小,堆可以放入内存
【基本原理及要点】
最大堆求前n小,最小堆求前n大。方法,比如求前n小,我们比较当前元素与最大堆里的最大元素,如果它小于最大元素,则应该替换那个最大元
素。这样最后得到的n个元素就是最小的n个。适合大数据量,求前n小,n的大小比较小的情况,这样可以扫描一遍即可得到所有的前n元素,效率很高。
【扩展】
双堆,一个最大堆与一个最小堆结合,可以用来维护中位数。
【问题实例】
1)100w个数中找最大的前100个数。
用一个100个元素大小的最小堆即可。
分享到:
相关推荐
GPU OpenFlow海量数据网络处理模型——GOMDI.pdf
解决海量数据的新思路——分布式数据库收集.pdf
海量数据是发展趋势,对数据分析和挖掘也越来越重要,从海量数据中提取有用信息重要而紧迫,这便要求处理要准确,精度要高,而且处理时间要短,得到有价值信息要快,所以,对海量数据的研究很有前途,也很值得进行...
讲解在面试中经常出现的海量数据处理的解决方案,思路清晰,内容详实。
海量数据处理方法
包含各种不常见的海量数据处理算法和相应的数据结构。确实是一本好资料啊
介绍了一个海量数据处理的面试题,也对海量数据处理方法进行了总结。
海量数据处理:十道面试题与十个海量数据处理方法总结
面向物联网的海量数据处理研究
十道海量数据处理面试题与十个方法大总结,主要面向互联网海量数据应用,海量数据筛选,排序等
hadoop海量数据处理技术详解,包括hdfs、MapReduce、hive、sqoop等相关技术和伪代码,代码是使用python语言写的。
海量数据处理分析方法,面试过程中非常有用的知识,尤其对于检索相关的工作
本书介绍了Hadoop技术的相关知识,并将理论知识与实际项目相结合。全书共分为三个部分:基础篇、应用篇和总结篇。
海量数据处理相关 所谓海量数据处理,是指基于海量数据的存储、处理、和操作。正因为数据量太大,所以导致要么无 法在较短时间内迅速解决,要么无法一次性装入内存。 事实上,针对时间问题,可以采用巧妙的算法搭配...
海量数据处理的机遇与挑战(info)!海量数据处理的机遇与挑战(info)
大数据量海量数据处理.pdf 很值得一看,收获颇多
有心去做百度、阿里巴巴、腾讯的可以参考下,总结了一些海量数据的处理方法
数据量的问题是很多面试笔试中经常出现的问题,比如 baidu google 腾讯 这样的一些 涉及到海量数据的公司经常会问到。...本贴从解决这类问题的方法入手,开辟一系列专题来解决海量数据问题。拟包含 以下几个 方面。
网上很多的海量数据处理分析资料,整理成word,面试使用
Hadoop与大数据技术大会(HadoopBigData Technology Conference 2012,HBTC 2012)于2012年11月30日-...在12月1日的主题论坛三上,网易资深工程师顾费勇为我们带来了题为《海量数据搬运工——DataStream》的主题演讲。