w****o
发帖数: 2260 | 1 哪本书？或者是哪个link, tutorial讲这个的？谢谢！ | c*****r
发帖数: 108 | 2 你是说k个sorted array merge么？ 用heap/priorityqueue的那个？ | w****o
发帖数: 2260 | 3 对，我问的就是k个sorted array merge,能给些资料吗？
还有个问题，大家知道merge sort用到了merge 两个sorted arrays,通常这两个sorted
arrays在内存里是连在一起的(contigous)。
那么对于这个k个sorted array merge,这些 k 个sorted arrays在内存里是连在一起的
吗？还是分开的？
【在 c*****r 的大作中提到】
: 你是说k个sorted array merge么？ 用heap/priorityqueue的那个？
| L***Q
发帖数: 508 | 4 k-way merge的内存不见得是连续的，比如外部排序，只能一部分读进内存。
LeetCode上有一个online judge （http://www.leetcode.com/onlinejudge）的题，Merge k Sorted Lists，可以拿来练习。
sorted
【在 w****o 的大作中提到】
: 对，我问的就是k个sorted array merge,能给些资料吗？
: 还有个问题，大家知道merge sort用到了merge 两个sorted arrays,通常这两个sorted
: arrays在内存里是连在一起的(contigous)。
: 那么对于这个k个sorted array merge,这些 k 个sorted arrays在内存里是连在一起的
: 吗？还是分开的？
| g*********e
发帖数: 14401 | | i**********e
发帖数: 1145 | 6 这个contiguous或者不是contiguous关系不大，你可以用个二维数组来表示k 个sorted
arrays（如果不同长度的话那就浪费一些空间了）。这样的话 第 i 个array和第j个
array的头在内存里也不是连续的。
如果真要考虑连续而影响caching performance 的话就不是那么简单的问题了，要考虑
cache memory 有多少 architecture 等等的底层东西了。
sorted
【在 w****o 的大作中提到】
: 对，我问的就是k个sorted array merge,能给些资料吗？
: 还有个问题，大家知道merge sort用到了merge 两个sorted arrays,通常这两个sorted
: arrays在内存里是连在一起的(contigous)。
: 那么对于这个k个sorted array merge,这些 k 个sorted arrays在内存里是连在一起的
: 吗？还是分开的？
|
|
