ruby - 懒惰地合并 ruby 中的N个排序数组

Question

如何在 Ruby 中延迟合并 N 个排序数组(或其他类似列表的数据结构)？例如，在 Python 中，您将使用 heapq.merge。 Ruby 中一定有这样的内置功能，对吧？

Answer 1

这里有一个(稍微打高尔夫球的)解决方案，它应该适用于任何支持 #first、#shift 和 # 的“类列表”集合的数组空？。请注意，它是破坏性的 - 每次调用 lazymerge 都会从一个集合中删除一项。

def minheap a,i
  r=(l=2*(m=i)+1)+1 #get l,r index
  m = l if l< a.size and a[l].first < a[m].first
  m = r if r< a.size and a[r].first < a[m].first
  (a[i],a[m]=a[m],a[i];minheap(a,m)) if (m!=i)
end


def lazymerge a
  (a.size/2).downto(1){|i|minheap(a,i)}
  r = a[0].shift
  a[0]=a.pop if a[0].empty?
  return r
end

p arrs = [ [1,2,3], [2,4,5], [4,5,6],[3,4,5]]
v=true
puts "Extracted #{v=lazymerge (arrs)}.  Arr= #{arrs.inspect}" while v

输出:

[[1, 2, 3], [2, 4, 5], [4, 5, 6], [3, 4, 5]]
Extracted 1.  Arr= [[2, 3], [2, 4, 5], [4, 5, 6], [3, 4, 5]]
Extracted 2.  Arr= [[3], [2, 4, 5], [4, 5, 6], [3, 4, 5]]
Extracted 2.  Arr= [[4, 5], [3], [4, 5, 6], [3, 4, 5]]
Extracted 3.  Arr= [[4, 5], [3, 4, 5], [4, 5, 6]]
Extracted 3.  Arr= [[4, 5], [4, 5], [4, 5, 6]]
Extracted 4.  Arr= [[5], [4, 5], [4, 5, 6]]
Extracted 4.  Arr= [[5], [5], [4, 5, 6]]
Extracted 4.  Arr= [[5, 6], [5], [5]]
Extracted 5.  Arr= [[6], [5], [5]]
Extracted 5.  Arr= [[5], [6]]
Extracted 5.  Arr= [[6]]
Extracted 6.  Arr= [[]]
Extracted .  Arr= [[]]

另请注意，此算法在维护堆属性方面也是惰性的 - 它不会在调用之间维护。这可能会导致它做比需要更多的工作，因为它会在每个后续调用中进行完整的堆化。这可以通过预先执行一次完整的 heapify，然后在 return r 行之前调用 minheap(a,0) 来解决。