合并N个排序的数组在ruby懒惰

Question

如何在Ruby中懒洋洋地合并N个排序数组(或其他类似列表的数据结构)？例如,在Python中,您将使用heapq.merge.Ruby中必须有这样的内容,对吧？

Answer 1

我最终使用“算法”gem 中的数据结构自己编写了它。情况并没有我想象的那么糟糕。

require 'algorithms'

class LazyHeapMerger
  def initialize(sorted_arrays)
    @heap = Containers::Heap.new { |x, y| (x.first <=> y.first) == -1 }
    sorted_arrays.each do |a|
      q = Containers::Queue.new(a)
      @heap.push([q.pop, q])
    end
  end

  def each
    while @heap.length > 0
      value, q = @heap.pop
      @heap.push([q.pop, q]) if q.size > 0
      yield value
    end
  end
end

m = LazyHeapMerger.new([[1, 2], [3, 5], [4]])
m.each do |o|
  puts o
end