算法 K-Way 合并。这个解决方案是 O(n log k) 吗？

Question

所以问题是使用最小堆将 k 个排序列表（假设它们按升序排序）合并到 1 个 n 元素列表中。现在我找到了解决方案，但不确定它是否可以有运行时间的 nlogk。这是我的伪代码，你们怎么看？

Algorithm kWayMerge(S)
  t ← 0
  Result ← ∅
  while t ≤ n do
      choosenHeap ← min(S1[1], … Sk[1])
      t ← t + 1
      Result[t] ← DeleteMin(choosenHeap)
  end loop
end

Function DeleteMin(H)
  Min ← A[1]
  A[1] ← A[size[H]]
  size[H] ← size[H] - 1
  DownHeap(H, 1)
  return Min
end

Function DownHeap(A, t)
  c ← 2*t
  if c > size[A] then
      return
  if c+1 > size[A] && A[c] > A[c + 1] then
      c ← c + 1
  temp ← A[t]
  A[t] ← A[c]
  A[c] ← temp
  DownHeap(A, c)
end

基本上我的解决方案是搜索k个列表并找到具有最小根值的Min Heap并将其放入结果数组中。基本上，由于从给定的 k 个排序列表中删除所有元素，kWayMerge 中的外循环将迭代 n 次。

Answer 1

您提出的算法称为 Ideal Merge technique for k-way merge, and indeed runs in O(n log(k)), assuming the min-heap is implemented with a logarithmic data structure (e.g., a binary heap。

堆被访问Θ(n)次，因为每一项恰好被插入和提取一次。
堆在每个点最多包含 k 个元素（请注意，某些列表可能 "depleted" 在其他列表之前）。
所有其他操作都是每个元素的常数时间。

所以，如果每次访问堆是O(log(k'))，其中k'是访问的次数堆中的元素，则总海岸为 O(n log(k)).

Answer 2

Min 也有运行时间，这里是 O(k)

所以它的 O(nk logk)

算法 K-Way 合并。这个解决方案是 O(n log k) 吗？

Algorithm K-Way Merge. Would this solution be O(n log k)?

algorithm

pseudocode