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