【什么是堆】
概念:堆是一种特殊的二叉树,具备以下两种性质
1)每个节点的值都大于(或者都小于,称为最小堆)其子节点的值
2)树是完全平衡的,并且最后一层的树叶都在最左边
这样就定义了一个最大堆。如下图用一个数组来表示堆:
那么下面介绍二叉堆:二叉堆是一种完全二叉树,其任意子树的左右节点(如果有的话)的键值一定比根节点大,上图其实就是一个二叉堆。
你一定发觉了,最小的一个元素就是数组第一个元素,那么二叉堆这种有序队列如何入队呢?看图:
假设要在这个二叉堆里入队一个单元,键值为2,那只需在数组末尾加入这个元素,然后尽可能把这个元素往上挪,直到挪不动,经过了这种复杂度为Ο(logn)的操作,二叉堆还是二叉堆。
那如何出队呢?也不难,看图:
出队一定是出数组的第一个元素,这么来第一个元素以前的位置就成了空位,我们需要把这个空位挪至叶子节点,然后把数组最后一个元素插入这个空位,把这个“空位”尽量往上挪。这种操作的复杂度也是Ο(logn)。
【适用范围】
海量数据前n大,并且n比较小,堆可以放入内存
【基本原理及要点】
最大堆求前n小,最小堆求前n大。方法,比如求前n小,我们比较当前元素与最大堆里的最大元素,如果它小于最大元素,则应该替换那个最大元 素。这样最后得到的n个元素就是最小的n个。适合大数据量,求前n小,n的大小比较小的情况,这样可以扫描一遍即可得到所有的前n元素,效率很高。
【扩展】
双堆,一个最大堆与一个最小堆结合,可以用来维护中位数。
【问题实例】
1)100w个数中找最大的前100个数。
用一个100个元素大小的最小堆即可。
做人要厚道:转载请注明出处:http://blog.redfox66.com/post/2010/10/02/mass-data-topic-5-heap.aspx
相关推荐
可转债自动筛选软件,自动筛选出超短区间内可以盈利的可转债(适用于股市大涨阶段),依托于集思录的数据,雇人做了这么一个可转债自动筛选软件,因为是易语言写的软件,可能会报毒,但是实际上没有毒,因为我用它...
可转债助手,汇总可转债数据的软件
20210618-光大证券-光伏行业转债梳理:光伏转债扩容在即,细细梳理转债市场上的光伏企业.pdf
量化角度看可转债(四):转债定价与折价策略.
银河证券可转债权限开通答案
光伏行业转债梳理:光伏转债扩容在即,细细梳理转债市场上的光伏企业(16页).pdf
可转债投资.pdf
转债策略专题系列报告一:低价转债复盘,超低价的消失
[精选]可转债投资可转债.pptx
可转债条款和常用指标
可转债研究:两期并存转债的定价关系.pdf
转债入门手册之十:转债信用分析框架指南.pdf
金融行业研究方法-可转债专题报告—转债基础研究系列之二:转债监管变革的三生三世.pdf
其中分数布朗运动的Hurst 参数H 满足1/2 ,用于描述股价的长记忆性,利率服从Vasicek 过程,违约风险用约化方法处理,建立可转债定价模型. 通过引入投资者的风险偏好态度以及对效用函数的限制使得可转债的风险中性...
MBA资本市场案例分析南化转债PPT教案学习.pptx
可转债筛选工具excel表格版本
计算可转债双底指标并排序 根据防雷原则将部分标的剔除.结果写到excel里.
东北固收转债深度:特高压行业转债怎么看?.pdf
20210418-广发证券-2021转债行业梳理之五:金融行业转债大盘点.pdf
本报告对可转债收益预测框架进行了详细的分析和讨论,从偏债型、平衡型、偏股型转债投资者的诉求出发,讨论了各类型转债的核心优势和风险,并梳理出了“固收+”策略、追求 Alpha 的转债基金以及情绪交易者三种不同的...