Python max heap of strings

Question

The suggested method to have a max heap is to multiply the key with -1. What is the suggested method to have a max heap of strings?

Is there an alternative library that has that feature?

Answer 1

You could construct a maxheap from your strings by using heapq to build a minheap of string-like objects whose character content is the same as your original strings but whose comparison operators (and therefore their sort order) produce results that are the opposite of the normal string object. If we call that object a contra_string then it would be defined like this:

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

It would be used like this:

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']"

Bear in mind that the objects in the heap are instances of contra_string, so they'll behave strangely if you use them in comparisons after you pop them from the heap. If you need to do anything involving naturally-ordered string comparisons with those objects after extracting them then you can recover the original ordinary string by using the normal method on the contra_string, and of course comparisons using those original strings will behave normally. That would look like:

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'>"

Answer 2

Create your own custom string class:

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

And use it like:

heapq.heappush(heap, MyString(word))