如何在Ruby中实现优先队列/堆并解决高频单词排序问题？

嘿，我明白你的问题了：你用group_by加sort_by的方法得到的结果不符合预期，因为当单词频率相同时，你需要按字母顺序优先选靠前的（比如"code"而不是"leet"），同时还想不用gem实现堆/优先队列，适配在线编程测试的场景。下面分两种方案来解决：

一、快速修复现有代码（小数据量首选） #

你当前代码的问题很明确：频率相同时没考虑字母序排序。原sort_by只按-s.length（频率降序）排序，当多个单词频率一样时，会保留它们在group_by后的原始插入顺序（也就是原数组里先出现的单词排在前面），所以才会选出"leet"而不是"code"。

只需要给sort_by加个次要排序规则就行，让它先按频率降序，再按单词的字母升序排序：

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

result = words.group_by(&:itself)
              .sort_by { |word, counts| [-counts.length, word] }
              .first(k)
              .map(&:first)

puts result.inspect # => ["i", "love", "code"]

这里的[-counts.length, word]是关键：

• 第一优先级是-counts.length，频率越高的单词越靠前
• 第二优先级是word，当频率相同时，字母序越靠前的单词（比如"code"比"leet"早）会被排在前面

这个方案简单直接，适合数据量不大的场景，代码可读性也很高。

二、用优先队列/堆实现（大数据量高效方案） #

如果要处理的单词数量特别大，全量排序的O(n log n)复杂度可能不够高效，这时用最小堆来维护前k个高频单词，时间复杂度可以降到O(n log k)，更适合在线编程测试中的大数据输入场景。下面是纯Ruby实现，不需要任何第三方gem：

实现思路 #

1. 先统计每个单词的出现频率（还是用group_by，这个步骤省不了）
2. 维护一个大小为k的最小堆：
   • 堆里的每个元素是[频率, 单词]的数组
   • 堆的排序规则有点特殊：
     • 优先看频率，频率小的放在堆顶（这样堆顶是当前堆里频率最低的元素）
     • 如果频率相同，把字母序大的放在堆顶（这样当堆满时，我们可以弹出字母序更大的那个，保留更小的）
3. 遍历所有单词的频率对：
   • 堆的大小小于k时，直接把当前元素加进去
   • 如果当前单词的频率比堆顶高，或者频率相同但字母序比堆顶小，就弹出堆顶，把当前元素加进去
4. 最后把堆里的元素按频率降序、字母升序整理，得到最终结果

完整代码实现 #

class MinHeap
  def initialize
    @elements = []
  end

  def size
    @elements.size
  end

  def peek
    @elements.first
  end

  def push(item)
    @elements << item
    bubble_up(@elements.size - 1)
  end

  def pop
    swap(0, @elements.size - 1)
    item = @elements.pop
    bubble_down(0)
    item
  end

  private

  def bubble_up(index)
    parent_index = (index - 1) / 2
    return if index <= 0 || compare(@elements[parent_index], @elements[index]) <= 0

    swap(index, parent_index)
    bubble_up(parent_index)
  end

  def bubble_down(index)
    left_child_index = index * 2 + 1
    right_child_index = index * 2 + 2
    smallest = index

    smallest = left_child_index if left_child_index < size && compare(@elements[left_child_index], @elements[smallest]) < 0
    smallest = right_child_index if right_child_index < size && compare(@elements[right_child_index], @elements[smallest]) < 0

    return if smallest == index

    swap(index, smallest)
    bubble_down(smallest)
  end

  # 自定义堆的比较规则
  def compare(a, b)
    # 先比频率，频率小的优先级高（堆顶是最小频率）
    freq_compare = a[0] <=> b[0]
    return freq_compare unless freq_compare == 0

    # 频率相同时，字母序大的优先级高（这样堆顶是字母最大的，方便弹出）
    b[1] <=> a[1]
  end

  def swap(i, j)
    @elements[i], @elements[j] = @elements[j], @elements[i]
  end
end

# 主逻辑
words = ["i", "love", "leet", "i", "love", "code"]
k = 3

# 统计每个单词的频率
frequency_map = words.group_by(&:itself).transform_values(&:size)

heap = MinHeap.new

frequency_map.each do |word, freq|
  if heap.size < k
    heap.push([freq, word])
  else
    top_freq, top_word = heap.peek
    # 判断是否需要替换堆顶：当前频率更高，或者频率相同但字母序更小
    if freq > top_freq || (freq == top_freq && word < top_word)
      heap.pop
      heap.push([freq, word])
    end
  end
end

# 把堆里的元素按要求排序后提取单词
result = heap.instance_variable_get(:@elements).sort_by { |freq, word| [-freq, word] }.map(&:last)
puts result.inspect # => ["i", "love", "code"]

代码说明 #

• MinHeap类是核心，自定义的compare方法确保堆的排序符合我们的需求：堆顶始终是当前最应该被替换的元素（要么频率最低，要么频率相同但字母序最大）
• 遍历频率映射时，严格控制堆的大小不超过k，确保只保留前k个符合要求的单词
• 最后对堆内元素做一次排序，把它们调整成频率降序、字母升序的顺序，得到最终结果

这个方案既满足了你的排序要求，又用堆实现了更高效的处理，完全适配在线编程测试的场景。

内容的提问来源于stack exchange，提问作者tk0221