How to make heapq evaluate the heap off of a specific attribute?
heapq
sorts objects the same way list.sort
does, so just define a method __cmp__()
within your class definition, which will compare itself to another instance of the same class:
def __cmp__(self, other):
return cmp(self.intAttribute, other.intAttribute)
Works in Python 2.x.
In 3.x use:
def __lt__(self, other):
return self.intAttribute < other.intAttribute
According to the Official Document, a solution to this is to store entries as tuples (please take a look at Section 8.4.1 and 8.4.2).
For example, your object is something like this in tuple's format (key, value_1, value_2)
When you put the objects (i.e. tuples) into heap, it will take the first attribute in the object (in this case is key) to compare. If a tie happens, the heap will use the next attribute (i.e. value_1) and so on.
For example:
import heapq
heap = []
heapq.heappush(heap, (0,'one', 1))
heapq.heappush(heap, (1,'two', 11))
heapq.heappush(heap, (1, 'two', 2))
heapq.heappush(heap, (1, 'one', 3))
heapq.heappush(heap, (1,'two', 3))
heapq.heappush(heap, (1,'one', 4))
heapq.heappush(heap, (1,'two', 5))
heapq.heappush(heap, (1,'one', 1))
show_tree(heap)
Output:
(0, 'one', 1)
(1, 'one', 1) (1, 'one', 4)
(1, 'one', 3) (1, 'two', 3) (1, 'two', 2) (1, 'two', 5)
(1, 'two', 11)
About pretty print a heap in python (updated the link): show_tree()
According to the example from the documentation, you can use tuples, and it will sort by the first element of the tuple:
>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')
So if you don't want to (or can't?) do a __cmp__
method, you can manually extract your sorting key at push time.
Note that if the first elements in a pair of tuples are equal, further elements will be compared. If this is not what you want, you need to ensure that each first element is unique.