F**********r
发帖数: 237 | 1 这回这个问题可能和具体实现有关，就是k-way merge。
1）首先如果能够全部load进内存，是不是其实最好就是依序把它们放进连续内存，然
后直接sort。O(nlogn)
如果用heap的话，要么就是heap的每个element要有data+index（2.1),要么就是要有一
个size k的array存放每个array的active index,但是要决定具体要advance which
array的时候，worst case要把size k array所指向的element和heap top比较一次(2.2
)：这本身复杂度就是k*n了。。。。另外虽然heap move down直接成堆复杂度是O(n),
但并不适用在这个case。也就是说用堆的话复杂度是O（nlogk)+ 更多内存 或者 O(n*k
).
这个理解对么？大家怎么看？ |
l*********8
发帖数: 4642 | 2 不理解你的这句：
"worst case要把size k array所指向的element和heap top比较一次(2.2
)：这本身复杂度就是k*n了"
每次把heap top的元素输出，然后从这个元素来自的array中取一个元素，加入到heap
中。 每次 log(k), |
P********l
发帖数: 452 | 3
不是。直接sort没有利用每个array已经排序的条件。
对。
要么就是要有一
.2
没听说过。
另外虽然heap move down直接成堆复杂度是O(n),
*k
【在 F**********r 的大作中提到】
: 这回这个问题可能和具体实现有关，就是k-way merge。
: 1）首先如果能够全部load进内存，是不是其实最好就是依序把它们放进连续内存，然
: 后直接sort。O(nlogn)
: 如果用heap的话，要么就是heap的每个element要有data+index（2.1),要么就是要有一
: 个size k的array存放每个array的active index,但是要决定具体要advance which
: array的时候，worst case要把size k array所指向的element和heap top比较一次(2.2
: )：这本身复杂度就是k*n了。。。。另外虽然heap move down直接成堆复杂度是O(n),
: 但并不适用在这个case。也就是说用堆的话复杂度是O（nlogk)+ 更多内存 或者 O(n*k
: ).
: 这个理解对么？大家怎么看？
|
F**********r
发帖数: 237 | 4 嗯，那个k size array是我看的网上的一个implementation, 当时就晕了。。。。想说
这也不快啊。。。。
【在 P********l 的大作中提到】
:
: 不是。直接sort没有利用每个array已经排序的条件。
: 对。
: 要么就是要有一
: .2
: 没听说过。
: 另外虽然heap move down直接成堆复杂度是O(n),
: *k
|
F**********r
发帖数: 237 | 5 en，就是我在网上发现一个implementation。他的heap本身是没有多余的index info.
所以为了找到即将被remove的heap element属于哪个array，要用一个k size array记
录每个array 的active element然后比较，我看了很晕，觉得好像不是很好。。。
heap
【在 l*********8 的大作中提到】
: 不理解你的这句：
: "worst case要把size k array所指向的element和heap top比较一次(2.2
: )：这本身复杂度就是k*n了"
: 每次把heap top的元素输出，然后从这个元素来自的array中取一个元素，加入到heap
: 中。 每次 log(k),
|
h**********d
发帖数: 4313 | 6 如果是linked list，就用next指针就好了吧
【在 F**********r 的大作中提到】
: en，就是我在网上发现一个implementation。他的heap本身是没有多余的index info.
: 所以为了找到即将被remove的heap element属于哪个array，要用一个k size array记
: 录每个array 的active element然后比较，我看了很晕，觉得好像不是很好。。。
:
: heap
|
F**********r
发帖数: 237 | 7 那到是行
【在 h**********d 的大作中提到】
: 如果是linked list，就用next指针就好了吧
|
