堆排序(转换为求前5G大的元素)
处理海量数据常用【堆排序】:
(1)不需要一次性将所有数据加载到内存中;
(2)不用对所有元素进行排序,只需要和堆的根结点比较大小即可;
(3)对于海量数据而言,要求前k小/大的数,我们只需要构建一个k个大小的堆,然后将读入的数依次和根节点比较就行了(当然这里的前提是内存需要存的下k个数)
最大堆求前n小,最小堆求前n大。
1、前k小:
构建一个k个数的最大堆,当读取的数大于根节点时,舍弃;当读取的数小于根节点时,替换根节点,重新塑造最大堆,然后继续读取,最后读取完所有的数据之后,最大堆中的数就是最小k个数
2、前k大:
构建一个k个数的最小堆,当读取的数小于根节点时舍弃;当读取的数大于根节点时,替换根节点,重新塑造最小堆,然后继续读取,读取完所有的数据之后,最小堆中的数就是最大k个数
所以我们本题采用堆排序来求中位数
对于10G的数据,它的中位数就是第5G个元素,按常理来说我们需要构建一个5G大小的堆,但是允许的内存只有两个G,所以我们先构建一个1G大小的大顶堆,然后求出第1G个元素(根节点),然后利用该元素构建一个新的1G大小的堆,求出第2G大的元素,依次类推,求出第5G大的元素
每次构建一个堆求第几G大的元素,都需要重新遍历完所有10G的数据,相当于要遍历5 * 10G次,这需要频繁的IO操作,需要不断的从硬盘中读取数据
另外
还有其他方法,参考(https://zhuanlan.zhihu.com/p/75397875)