h***r
发帖数: 273 | 1 版上曾经出现的一道题，没想出正确解法，大牛们讨论讨论，指点一下
给两个部分排序的文件和partially sorted的值m，部分排序是定义为比如1 2 4 5
6 7 3， 3应该在2后面，那么3的partially sorted的值就是4.因为最多放在该点前面
4个index的位置。要实现两个file merge的输出，要输出的file是排序的。限制是file
很大很大，不能放在内存里面处理。 | r***3
发帖数: 3 | 2 只有最后一个数字是乱序的么？
如果m不是很大，可以每次读m+1个数字，在缓存中，如果发现最后一个数字小于第一个
数字，就把最后一个数字先比较。
file
【在 h***r 的大作中提到】
: 版上曾经出现的一道题，没想出正确解法，大牛们讨论讨论，指点一下
: 给两个部分排序的文件和partially sorted的值m，部分排序是定义为比如1 2 4 5
: 6 7 3， 3应该在2后面，那么3的partially sorted的值就是4.因为最多放在该点前面
: 4个index的位置。要实现两个file merge的输出，要输出的file是排序的。限制是file
: 很大很大，不能放在内存里面处理。
| a****a
发帖数: 15 | 3 应该是两个size为m的min-heap（这样能确保min再其中一个heap里面）
heap 1 负责 file 1, heap 2 负责 file 2
每次extract min(root1, root2) 写到 f3, 然后insert new value into the heap
直到file读完 heaps 都为空
至于内存限制.... f3 写的差不多了 就存到disk一下 |
|
