So I have lists of lists getting added to the heap; eg:
n = [[1, 5, 93],[2, 6, 44],[4, 7, 45],[6, 3, 12]]heapq.heapify(n)print(n)
This compares and sorts according to the list's first element.
My question is, how do I sort the heapq so it compares the third element of each list? For example, the above list would be accessed from the heapq in this order:
[[6, 3, 12],[2, 6, 44],[4, 7, 45],[1, 5, 93]]
heapq
doesn't support a key
function for it's ordering so you will need to manipulate your data structure. Mapping your list to a tuple(sort_value, list)
will allow you to do log(n)
push and pop:
In []:q = [(x[2], x) for x in n]heapq.heapify(q)heapq.heappop(q)Out[]:(12, [6, 3, 12])In []:l = [2, 5, 1]heapq.heappush(q, (l[2], l))heapq.heappop(q)Out[]:(1, [2, 5, 1])
Alternatively, define your own list
and implement the comparison function for that list:
class MyList(list):def __lt__(self, other):return self[2] < other[2]q = [MyList(x) for x in n]
Note: you should implement the other comparison functions (see functools.total_ordering
on how to do that easily).