10G数中找到前5G大的数

堆排序（转换为求前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）

5G

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。