10G數(shù)中找到前5G大的數(shù)

堆排序（轉(zhuǎn)換為求前5G大的元素）

處理海量數(shù)據(jù)常用【堆排序】：

（1）不需要一次性將所有數(shù)據(jù)加載到內(nèi)存中；

（2）不用對所有元素進行排序，只需要和堆的根結(jié)點比較大小即可；

（3）對于海量數(shù)據(jù)而言，要求前k小/大的數(shù)，我們只需要構(gòu)建一個k個大小的堆，然后將讀入的數(shù)依次和根節(jié)點比較就行了（當然這里的前提是內(nèi)存需要存的下k個數(shù)）

最大堆求前n小，最小堆求前n大。

1、前k小：

構(gòu)建一個k個數(shù)的最大堆，當讀取的數(shù)大于根節(jié)點時，舍棄；當讀取的數(shù)小于根節(jié)點時，替換根節(jié)點，重新塑造最大堆，然后繼續(xù)讀取，最后讀取完所有的數(shù)據(jù)之后，最大堆中的數(shù)就是最小k個數(shù)

2、前k大：

構(gòu)建一個k個數(shù)的最小堆，當讀取的數(shù)小于根節(jié)點時舍棄；當讀取的數(shù)大于根節(jié)點時，替換根節(jié)點，重新塑造最小堆，然后繼續(xù)讀取，讀取完所有的數(shù)據(jù)之后，最小堆中的數(shù)就是最大k個數(shù)

所以我們本題采用堆排序來求中位數(shù)

對于10G的數(shù)據(jù)，它的中位數(shù)就是第5G個元素，按常理來說我們需要構(gòu)建一個5G大小的堆，但是

允許的內(nèi)存只有兩個G

，所以我們先構(gòu)建一個1G大小的大頂堆，然后求出第1G個元素（根節(jié)點），然后利用該元素構(gòu)建一個新的1G大小的堆，求出第2G大的元素，依次類推，求出第5G大的元素

每次構(gòu)建一個堆求第幾G大的元素，都需要重新遍歷完所有10G的數(shù)據(jù)，相當于要遍歷5 * 10G次，這需要頻繁的IO操作，需要不斷的從硬盤中讀取數(shù)據(jù)

另外

還有其他方法，參考（https://zhuanlan.zhihu.com/p/75397875）

5G

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔相應法律責任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔相應法律責任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。