CODEWITHSUNDEEP
python
Aditya Pokharel
Aditya Pokharel

Reputation: 181

Python heapq : How do I sort the heap using nth element of the list of lists?

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

Upvotes: 9

Views: 12663

Answers (1)

AChampion
AChampion

Reputation: 30258

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).

Upvotes: 16

Related Questions