Python字符串最大堆

Question

创建最大堆的建议方法是将键与-1相乘。那么如何创建字符串的最大堆呢？

是否有其他库具有此功能？

- CS_EE

---

Python标准库提供了heapq。 - Green Cloak Guy

是的，但那是最小堆。我想要相反的。 - CS_EE

我认为这个问题非常合理，因为当前的heapq库不支持按某个参数的'max heap'。点赞！ - JUNPA

Answer 1

创建自己的自定义字符串类：

class MyString:
    def __init__(self, word):
        self.word = word

    def __lt__(self, other):
        return self.word > other.word

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

并像这样使用：

heapq.heappush(heap, MyString(word))    

- me_astr

---

这应该是一个通用的Reverse类，就像Rust一样。 - serg06

Answer 2

您可以使用heapq构建一个最大堆，以字符串为对象建立一个最小堆，这些字符串对象的字符内容与您原始的字符串相同，但它们的比较操作符（因此其排序顺序）生成的结果与正常字符串对象相反。如果我们将该对象称为contra_string，则它将被定义为：

class contra_string(str):

    def __init__(self, s):
       self.original = s

    def __lt__(self, s):
        return self.original.__gt__(s)

    def __le__(self, s):
        return self.original.__ge__(s)

    def __eq__(self, s):
        return self.original.__eq__(s)

    def __ne__(self, s):
        return self.original.__ne__(s)

    def __gt__(self, s):
        return self.original.__lt__(s)

    def __ge__(self, s):
        return self.original.__le__(s)

    def normal(self):
        return self.original

它将会被这样使用：

import heapq

mystrings = [ 'b', 'c', 'a', 'bravo', 'alpha', 'charlie' ]

maxheap = [contra_string(s) for s in mystrings]
heapq.heapify(maxheap)

print [heapq.heappop(maxheap) for n in range(len(maxheap))]
# prints "['charlie', 'c', 'bravo', 'b', 'alpha', 'a']"

记住，在堆中的对象是contra_string实例，所以如果您在从堆中弹出它们后在比较中使用它们，它们会表现得很奇怪。如果您需要在提取这些对象后执行任何涉及自然排序字符串比较的操作，则可以使用contra_string上的normal方法恢复原始普通字符串，并且使用这些原始字符串进行比较将表现正常。代码如下：

original_strings_in_reverse_order = [heapq.heappop(maxheap).normal() for n in range(len(maxheap))]
print type(original_strings_in_reverse_order[0])
# prints "<type 'str'>"

- ottomeister

Answer 3

只是想发布一个更简短的版本@me_astr's answer，使用相同的自定义类技术。在这种情况下，我只是扩展了str类并覆盖了heapq类使用的__lt__方法以反转它：

class ContraStr(str):
    def __lt__(self, s):
        return self.__gt__(s)

str_heap: list[ContraStr] = []
for word in ['c', 'aa', 'b', 'd', 'a']:
    heapq.heappush(str_heap, ContraStr(word))
print(str_heap)

以上内容输出为：

['d', 'c', 'b', 'aa', 'a']

请注意，就像@ottomeister所说的那样，您在稍后使用这些ContraStr对象时必须小心，因为比较将是相反的。例如，如果您想从堆中获得按正常顺序排序的列表，则需要以相反的顺序进行排序。

print(sorted(str_heap, reverse=True))

# prints ['a', 'aa', 'b', 'c', 'd']

- takanuva15

Answer 4

通过将字符值变为负数来反转字符串？全小写字符串的示例密钥：

lambda s: ''.join(chr(ord('z') - ord(c) + ord('a')) for c in s)

- Green Cloak Guy

---

如果 s1 = "a"，s2 = "aa"，你应该考虑长度。 - JUNPA