Python - how to sort Priority Queue by second argument

The implementation of Queue.PriorityQueue relies on heappush(), which doesn't provide a way to handle custom sorting.

You could subclass PriorityQueue and use a little hack to make this work without breaking functionnality:

from queue import PriorityQueue

class CustomPriorityQueue(PriorityQueue):
    def _put(self, item):
        return super()._put((self._get_priority(item), item))

    def _get(self):
        return super()._get()[1]


    def _get_priority(self, item):
        return item[1]

Test run:

>>> q = CustomPriorityQueue(100)
>>> q.put((2, 3, 5))
>>> q.put((2, 5, 5))
>>> q.put((2, 1, 5))
>>> q.put((2, 2, 5))
>>> q.get()
(2, 1, 5)
>>> q.get()
(2, 2, 5)
>>> q.get()
(2, 3, 5)
>>> q.get()
(2, 5, 5)

(Please note that this is python3 code)

from the documentation for Queue.py

There actually a PriorityQueue that automatically sort the elements in queue, but usually the elements are tuple structure (priority number, data)

I wrote some sample code here, it Q._pop() the tuple with smallest priority number:

import Queue

q = Queue.PriorityQueue()

print type(q)
print(q.queue)
q._put((4,'f'))
q._put((1,'c'))
q._put((5, 'a'))
q._put((10, 'b'))
q._put((6, 'd'))
print(q.queue)
q._get()
print(q.queue)
q._put((2,'f'))
print(q.queue)

The output is:

<type 'instance'>
[]
[(1, 'c'), (4, 'f'), (5, 'a'), (10, 'b'), (6, 'd')]
[(4, 'f'), (6, 'd'), (5, 'a'), (10, 'b')]
[(2, 'f'), (4, 'f'), (5, 'a'), (10, 'b'), (6, 'd')]

One thing I notice is that for the first time we print the q.queue, before we do any _get(), it doesn't show ordered queue, but once we call _get(), it always gives ordered queue.

From the documentation it appears that priority queue does not support custom ordering. A basic work around would be to create a wrapper object around your tuples and set the custom ordering in there

class Wrapper(object):
    def __init__(self, source):
        self.source = source

    def __cmp__(self, other):
        if self[1] == other[1]:
            return cmp(self.source, other.source)
        else:
            return cmp(self[1], other[1])

    def __getitem__(self, index):
        return self.source[index]

    def __len__(self):
        return len(self.source)

    def __repr__(self):
        return self.source.__repr__()

This is merely an example, and you should take care of edge cases where the other object is a tuple, a list, an empty tuple and a tuple with one element.

You can simply add a Wrapper class only with the __ls__ method:

class MyObj:
  def __init__(self, key=None, data=None):
    self.key = key
    self.data = data

class Wrapper:
  def __init__(self, obj):
    self.obj = obj

  def __lt__(self, other):
    return self.obj.key < other.obj.key

And then add the object like this:

p = PriorityQueue()
p.put(Wrapper(MyObj(key=(3,5), data=(2,3,5))))
value = p.get().obj.data

To be noted that this works will all the sortedcontainers in Python. You can also obtain a maxheap by changing return self.obj.key < other.obj.key to return self.obj.key > other.obj.key!