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

Question

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

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

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

Answer 1

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

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

Answer 2

我就有一个疑问，这种题难道不能用位图来做。。。
1、遍历这10G个数字，在位图里做标记哪些出现过，同时统计具体出现过多少个不同的数字，记为count
2、遍历位图，找到第 count/2 个bit，就是这个数。。。

如果整数是 0 ~ 2^32-1这种4byte的。那么存下它的取值范围，只需要512M内存的位图吧。。。。?

Answer 3

关于这个方法我还有些发散的问题，如果大神们觉得有意思可以看一下：
既然分成了10个堆，那么普遍情况每个堆的边界值是多少？

分成十堆的话，最差情况下快速排序需要多少次判断？

是否还可以减少计算量？

@zonxin