heapq.heappush() 是否比较未指定的 int AND 字符串？

Question

我正在检查这个关于 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 它正确 returns ["a"]。我的问题是堆是否也在内部按字典顺序对元组进行排序？因为根据我的说法，如果没有排序，它只会返回 ["aa"]（堆的构建顺序，因为所有三个的计数都相同）。还是我误解了heapq?

Answer 1

您有一堆 integer/string 对，因此它根据元组的 < 定义进行排序，其中考虑了每种类型的两个元素。

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

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

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

Answer 2

堆是偏序的。它们没有排序。但是，您可以通过将值存储在堆中并一次将它们取出一个来构建它们的排序。这些排序不稳定，因为堆不会尝试保留 "equal" 值的顺序。

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

Answer 3

heapq 只是使用“小于”运算符 ^[1] 比较队列中的值，而不考虑值的类型。它是定义比较内容的值的类型 return。所以，这里的区别在于元组本身。从 the documentation 开始：

The comparison [of sequence objects] uses lexicographical ordering: first the first two items are compared, and if they differ this determines the outcome of the comparison; if they are equal, the next two items are compared, and so on, until either sequence is exhausted.

检查一些示例：

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

所以你是对的，值是按字典顺序排列的，元组的第二个值是相关的。但是，heapq 不必在此处执行任何操作即可获得此结果，仅通过元组比较即可。

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

cmp = PyObject_RichCompareBool(newitem, parent, Py_LT);

这个PyObject_RichCompareBool()是，根据the documentation：

the equivalent of the Python expression o1 op o2, where op is the operator corresponding to opid.

Answer 4

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

我们希望 'minHeap' 将 'minimum frequency' 和 'max lexicographical' 值保持在堆的顶部。这很棘手，因为默认情况下它会保留 'minimum frequency' 和 'min lex'.

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

def __lt__(self, other):
    if self.c == other.c:
        return self.w > other.w
    return self.c < other.c

heapq.heappush() 是否比较未指定的 int AND 字符串？

Does heapq.heappush() compare on int AND string without been specified for?

python

python-3.x

heap

heapq