如何在 Ruby 中实现优先级队列或堆？

Question

我有：

words = ["i", "love", "leet", "i", "love", "code"]
k = 3

"i" 和 "love" 出现两次，但 "leet" 和 "code" 出现一次。我要：

["i", "love", "code"]

而不是 "leet"。此代码：

words.group_by(&:itself).sort_by {|_, s| -s.length}.first(k).map(&:first)

将显示：

["i", "love", "leet"]

解决这个问题的好方法是什么？

可以用heap解决，但是Ruby不支持Heap。有什么推荐吗？我想在不使用 gem 的情况下执行此操作，以便我可以在在线代码测试站点上进行演示。

============================================= ============================= k 是频率所以这道题是在words数组中找到k个频率词。当 k 为 3 时，我的计数器选择 code 而不是 leet。当有相同频率的词时，我想按字母顺序排序，所以我可以选择第一个。

Answer 1

如果要在频率相同时按字母顺序排序，按字母顺序排序:

words.group_by { |w| w }.
      sort_by { |w, a| [-a.size, w] }. # ⇐ HERE
      map(&:first).
      first(3)
#⇒ ["i", "love", "code"]

如何在 Ruby 中实现优先级队列或堆？

How can I implement priority queue or heap in Ruby?

ruby

heap