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

Question

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

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

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

Answer 1

Timbunan ialah struktur data, iaitu pokok binari yang lengkap (jadi tiada penuding diperlukan untuk menyimpan strukturnya setiap nod tidak lebih besar daripada atau tidak lebih kecil daripada nod anaknya, sepadan dengan timbunan atas yang besar dan timbunan atas yang kecil). masing-masing. Sebagai contoh, dalam timbunan atas yang kecil, unsur akar adalah yang terkecil. Jadi ia boleh digunakan sebagai O(1)的复杂度查找其中的最大或是最小的元素。其删除和插入元素的复杂度，最坏情况下都是O(log(N)).

Petikan ini bermakna dengan mula-mula mencipta timbunan atas kecil yang boleh menampung data (1G+1), anda boleh mencari elemen terkecil di dalamnya dengan cepat. Kemudian lintasi semua 10G data dan masukkannya: jika timbunan penuh selepas sisipan (terdapat data 1G+1 dalam timbunan). Hanya padamkan yang terkecil. . . .
Hasil akhir ialah data dalam timbunan adalah data 1G terbesar, dan bahagian atas timbunan adalah yang terkecil, iaitu, jika diisih dalam tertib menurun, kedudukan data ini ialah kedudukan 1G, contohnya, nombor ini ialah x.
Kemudian, teruskan proses di atas sekali lagi, tetapi perbezaannya ialah hanya elemen yang kurang daripada x dimasukkan ke dalam timbunan, dan elemen yang lebih besar daripada atau sama dengan x diabaikan. Iaitu, selepas mengabaikan data 1G yang baru ditemui, cari 1G terbesar. Dengan cara ini, bahagian atas timbunan terakhir ialah data pada kedudukan 2G selepas mengisih. (Tetapi berhati-hati apabila berurusan dengan data pendua). . . . Dan seterusnya untuk mencari median.

Answer 2

Saya ada soalan, bukankah soalan seperti ini boleh dilakukan menggunakan peta bit? . .
1. Lintas nombor 10G ini, tandakan yang mana yang telah muncul dalam bitmap, dan hitung berapa banyak nombor berbeza yang telah muncul, rekodkannya sebagai kiraan
2. Lintas bitmap, cari kiraan/bit ke-2, iaitu nombor ini. . .

Jika integer ialah 4bait seperti 0 ~ 2^32-1. Kemudian untuk menyimpan julat nilainya, anda hanya memerlukan bitmap memori 512M. . . . ?

Answer 3

Saya masih mempunyai beberapa soalan yang berbeza tentang kaedah ini Jika pakar mendapati ia menarik, anda boleh lihat:
Oleh kerana ia dibahagikan kepada 10 timbunan, apakah nilai sempadan sepunya bagi setiap timbunan?

Jika dibahagikan kepada sepuluh longgokan, berapa banyak penghakiman yang diperlukan untuk mengisih pantas dalam kes terburuk?

Adakah mungkin untuk mengurangkan jumlah pengiraan?

@zonxin