题目描述：
从 5 亿个数中找出中位数。数据排序后，位置在最中间的数就是中位数。当样本数为奇数时，中位数 =（N+1）/2；当样本数为偶数时，中位数为 N/2 与 1+N/2 的均值。
分析与解答：
如果这道题目没有内存大小的限制，则可以把所有的数字排序后找出中位数，但是最好的排序算法的时间复杂度都是 O（NlogN）（N 为数字的个数）。这里介绍另外一种求解中位数的算法——双堆法。
方法一：双堆法
这个算法的主要思路是维护两个堆，一个大顶堆，一个小顶堆，且这两个堆需要满足如下两个特性。
特性一：大顶堆中最大的数小于或等于小顶堆中最小的数。
特性二：保证这两个堆中的元素个数的差不能超过 1。
若数据总数为偶数时，当这两个堆建立好以后，中位数显然就是两个堆顶元素的平均值。当数据总数为奇数时，根据两个堆的大小，中位数一定在数据多的堆的堆顶。对本题而言，具体实现思路：维护两个堆 maxHeap 与 minHeap，这两个堆的大小分别为 max_size 和 min_size，然后开始遍历数字。对于遍历到的数字 data：
1）如果 data＜maxHeap 的堆顶元素，此时为了满足特性 1，只能把 data 插入到 maxHeap 中。为了满足特性二，需要分以下几种情况讨论。
① 如果 max_size≤min_size，则说明大顶堆元素个数小于小顶堆元素个数，此时把 data 直接插入大顶堆中，并把这个堆调整为大顶堆。
② 如果 max_size＞min_size，为了保持两个堆元素个数的差不超过 1，则需要把 maxHeap 堆顶的元素移动到 minHeap 中，接着把 data 插入到 maxHeap 中。同时通过对堆的调整，分别让两个堆保持大顶堆与小顶堆的特性。
2）如果 maxHeap 堆顶元素 ≤data≤minHeap 堆顶元素，则为了满足特性一，可以把 data 插入任意一个堆中，为了满足特性二，需要分以下几种情况讨论：
① 如果 max_size＜min_size，显然需要把 data 插入到 maxHeap 中；
② 如果 max_size＞min_size，显然需要把 data 插入到 minHeap 中；
③ 如果 max_size==min_size，可以把 data 插入到任意一个堆中。
3）如果 data＞maxHeap 的堆顶元素，此时为了满足特性一，只能把 data 插入到 minHeap 中。为了满足特性二，需要分以下几种情况讨论：
① 如果 max_size≥min_size，那么把 data 插入到 minHeap 中；
② 如果 max_size＜min_size，那么需要把 minHeap 堆顶元素移到 maxHeap 中，然后把 data 插入到 minHeap 中。
通过上述方法可以把 5 亿个数构建成两个堆，两个堆顶元素的平均值就是中位数。
由于需要把所有的数据都加载到内存中，当数据量很大时，因为无法把数据一次性加载到内存中，因此这种方法比较适用于数据量小的情况。对本题而言，5 亿个数字，每个数字在内存中占 4B，5 亿个数字需要的内存空间为 2GB 内存。当可用的内存不足 2GB 时，显然不能使用这种方法，下面介绍另外一种方法。
方法二：分治法
分治法的核心思想是把一个大的问题逐渐转换为规模较小的问题来求解。对于本题而言，顺序读取这 5 亿个数字；
1）对于读取到的数字 num，如果它对应的二进制中最高位为 1，则把这个数字写入到 f1 中，如果最高位是 0，则写入到 f0 中。通过这一步就可以把这 5 亿个数字划分成两部分，而且 f0 中的数字都大于 f1 中的数字（因为最高位是符号位）。
2）通过上面的划分很容易知道中位数是在 f0 中还是在 f1 中。假设 f1 中有 1 亿个数，那么中位数一定在文件 f0 中，且它的值为 f0 文件中的数字排序的第 1.5 亿个数与它后面一个数的平均值。
3）对于 f0，可以用次高位的二进制的值继续把这个文件一分为二，使用同样的思路可以确定中位数是哪个文件中的第几个数。直到划分后的文件可以被加载到内存时，把数据加载到内存中以后排序，从而找出中位数。
需要注意的是，这里有一种特殊情况需要考虑，当数据总数为偶数时，如果把文件一分为二后发现两个文件中的数据有相同的个数，那么中位数就是 f0 文件中的最大值与 f1 文件中的最小值的平均值。如果要求一个文件中所有数据的最大值或最小值，可以使用前面介绍的分治法进行求解。