javascript - 关于10G 个整数找出中位数，内存限制为 2G题目。-PHP中文网问答

腾讯有这么一道校招题：
只有2G内存的pc机，在一个存有10G个整数的文件，从中找到中位数，写一个算法。

有好几种解法，比如桶排序和基数排序，但是我查到有个利用堆来解决的方法，不太明白，原话是这么说的：
先求第1G大，然后利用该元素求第2G大，然后利用第2G大，求第3G大...当然这样的话虽不需排序，但是磁盘操作会比较多，具体还需要分析下与外排序的效率哪个的磁盘IO会比较多
建立一个1g个整数的最大值堆，如果元素小于最大值则入堆，这样可以得到第1g大的那个元素然后利用这个元素，重新建一次堆，这次入堆的条件还要加上大于这个第1g大的元素，这样建完堆可以得到第2g大的那个。

看的我一头雾水不得其法，先求1G大都没看明白是什么，是把10G的数据分成10份，然后把其中1G里的排序找出最大的意思么？
希望大家能指点我下这个解决方法的思路，谢谢了。

全部回复 (3)

PHPzhong2017-05-16 13:03:22 3 楼

堆是一种数据结构，是一棵完全二叉树（故保存其结构并不需要指针），每一个结点不大于或是不小于其子节点，分别对应大顶堆和小顶堆。比如，在小顶堆里面，根元素是最小的。所以其可以以O(1)的复杂度查找其中的最大或是最小的元素。其删除和插入元素的复杂度，最坏情况下都是O(log(N))。

这段话的意思是是说，先创建一个可以容纳（1G+1）个数据的小顶堆,即可以很快的找出其中的最小元素。然后遍历所有10G的数据，将其插入：如果插入后堆满了（堆中有了1G+1个数据）。就删除最小的那个。。。。
这样最后的结果就是，堆中的数据是最大的前 1G 个数据，并且堆顶是最小的那个，即如果降序排序，这个数据的位置是第1G的位置，比如这个数是 x。
然后，重新继续上述过程，但不同的是，只在堆中插入小于 x 的元素，忽略大于等于 x 的元素。即忽略刚才找出的那1G数据之后，在找出1G最大的。这样最终堆顶就是排序后第 2G 位置的数据。（但是要注意处理重复的数据）。。。。依次类推找出中位数。