惰性地将N个排序的数组合并到ruby中 [英] Merge N sorted arrays in ruby lazily

问题描述

一个人如何在Ruby中懒惰地合并N个排序数组(或其他类似列表的数据结构)?例如，在Python中，您将使用heapq.merge.一定是在Ruby中内置了类似的东西，对吧?

How does one merge N sorted arrays (or other list-like data structures) lazily in Ruby? For example, in Python you would use heapq.merge. There must be something like this built into Ruby, right?

推荐答案

我最终使用"algorithm" gem中的数据结构自己编写了它.并没有我想的那么糟.

I ended up writing it myself using the data structures from the 'algorithm' gem. It wasn't as bad as I expected.

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

这篇关于惰性地将N个排序的数组合并到ruby中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！