Is there a Lexicographic PriorityQueue in Python's standard library?

I have a set of pairs of numbers (i.e. 2-tuples) which I want to use as the priorities for a priority queue.

I found queue.PriorityQueue in the Python documentation, but examples I have seen of this class suggest that it is meant to take numbers rather than tuples. I also called help(PriorityQueue) and read that "Entries are typically tuples of the form: (priority number, data)".

>Solution :

The PriorityQueue data structure, and the heapq library it is based on, only use priorities for comparisons (i.e. <, <=, >, >=). The priorities can be any data type which supports those comparison operations.

In fact, this is exactly why a tuple of the form (priority, data) can be put into a priority queue at all – the queue doesn’t treat the different parts of the tuple differently, or directly look inside the tuple to extract its parts, or even check that it is a tuple. It just compares them, and that means first comparing their priorities (since the priority is the first element of the tuple).

This works the other way around, too – if each data item x is its own priority, then you can put x into the queue directly without having to wrap it in a tuple like (x, x).

Leave a Reply