覆盖Python3max堆

Question

我试图在Python 3中覆盖"max堆“，它不起作用。我已经重写了gt比较器。

它应该有一种在Python中实现这一目标的简单方法，对吗？

前两个项目的输出是'i', 'coding'，而期望项目是'i，爱‘。

这一点都说不通。不知道为什么Python模块如此令人困惑。

# ["i", "love", "leetcode", "i", "love", "coding"]

from collections import defaultdict
from heapq import heappush, _heappop_max, _heapify_max

class node(object):
    def __init__(self, cnt, word):
        self.cnt = cnt
        self.word = word

    def __lt__(self, other):
        return self.cnt < other.cnt

    def __gt__(self, other):
        return self.cnt > other.cnt

    def __eq__(self, other):
        return self.cnt ==  other.cnt

class Solution(object):
    def topKFrequent(self, words, k):
        """
        :type words: List[str]
        :type k: int
        :rtype: List[str]
        """
        heaped_words = []
        _heapify_max(heaped_words)
        counts = defaultdict(lambda: 0)
        results = []
        for i in words:
            counts[i] += 1
        for word, count in counts.items():
            heappush(heaped_words, node(count, word))

        while heaped_words:
            item = _heappop_max(heaped_words)
            if item:
                results.append(item.word)

        return results

Answer 1

您不需要为_heapmax_...使用API函数来实现最大堆。相反，您可以通过更改每个节点(即node(-count, word) )上的符号来交换将项推送到堆上的优先级。

那么，您的最大堆很容易变成：

from collections import Counter

def topKFrequent(words, k):
        """
        :type words: List[str]
        :type k: int
        :rtype: List[str]
        """
        counts = Counter(words)
        heaped_words = []
        for word, count in counts.items():
            heappush(heaped_words, node(-count, word))
        return [heappop(heaped_words).word for _ in range(k)]


lst = ["i", "love", "leetcode", "i", "love", "coding"]
print(topKFrequent(lst, 2))
# ['i', 'love']

注意，如果k几乎与输入列表的大小一样大，您可以在函数中提供一个分支指令，只需调用列表上的sorted并返回排序列表；这将比多个push和pops有效得多。