1

我在leetcode.com上查看这个问题的解决方案

def topKFrequent(self, words, k):
        count = collections.Counter(words)
        heap = [(-freq, word) for word, freq in count.items()]
        heapq.heapify(heap)
        return [heapq.heappop(heap)[1] for _ in xrange(k)]

当我为它提供一个字符串数组时["aa", "aaa", "a"]，1 它会正确返回["a"]. 我的问题是堆是否也在内部按字典顺序对元组进行排序？因为根据我的说法，如果没有排序，它会简单地返回["aa"]（构建堆的顺序，因为所有三个的计数都是相同的）。还是我误解了heapq？

4

4 回答 4

3

您有一堆整数/字符串对，因此它是根据<for 元组的定义进行排序的，它考虑了每种类型的两个元素。

给定["aa", "aaa", "a"]，count.items()是元组序列[('aa', 1), ('aaa', 1), ('a', 1)]。然后使用元组列表构建一个堆

[(-1, 'aa'), (-1, 'aaa'), (-1, 'a')]

由于每个元组的第一个元素相同，因此比较仅由第二个字符串元素确定。

于 2020-02-19T17:14:39.877 回答
2

heapq只需使用“小于”运算符[1]比较队列中的值，而不管值的类型。值的类型定义了比较将返回的内容。所以，这里的区别在于元组本身。从文档中：

[序列对象的]比较使用字典顺序：首先比较前两项，如果它们不同，则确定比较的结果；如果它们相等，则比较接下来的两项，依此类推，直到任一序列用完。

检查一些例子：

>>> (0, 'a') < (1, 'aa')
True
>>> (1, 'a') < (1, 'aa')
True
>>> (1, 'aa') < (1, 'a')
False
>>> (2, 'a') < (1, 'aa')
False

所以你是对的，这些值是按字典顺序排列的，并且元组的第二个值是相关的。然而，heapq这里不需要做任何事情来得到这个结果，仅仅是元组比较就可以了。

[1]可以在代码中查看。这是heapq（在 C 中）进行比较的行之一：

cmp = PyObject_RichCompareBool(newitem, parent, Py_LT);

这PyObject_RichCompareBool()是，根据文档：

相当于 Python 表达式 o1 op o2，其中 op 是对应于opid的运算符。

于 2020-02-19T17:40:32.700 回答
0

堆是部分排序。它们没有排序。但是，您可以通过将值存储在堆中并一次取出一个来对它们进行排序。这些排序并不稳定，因为堆不会尝试保持“相等”值的顺序。

这是您可能感兴趣的另一种 Python 堆： https ://pypi.org/project/fibonacci-heap-mod/

于 2020-02-19T17:14:54.000 回答
0

leetcode 问题的期望是在 O(nlogk) 内解决问题。所以我们必须随时在堆中只保留“k”个元素，这意味着我们必须使用“minHeap”（freq，word）而不是（-freq，word）。

我们希望“minHeap”将“最小频率”和“最大词典”值保持在堆的顶部。这很棘手，因为默认情况下它会保持“最小频率”和“最小 lex”。

唯一的解决方案是创建一个可以具有“freq”和“word”的对象并覆盖“ lt ”方法来执行此操作

def __lt__(self, other):
    if self.c == other.c:
        return self.w > other.w
    return self.c < other.c
于 2020-06-21T17:30:24.150 回答