CODEWITHSUNDEEP
python
Becay
Becay

Reputation: 103

Adding a custom object to a Priority queue in Python

I want to add Node objects to Python's PriorityQueue in Python 2. The Node objects should be prioritized according to the val attribute:

class ListNode:
     def __init__(self, val=0, next=None):
         self.val = val
         self.next = next

I am not allowed to tamper with this ListNode class so I do not have the option to add the __lt__ method to it.

Upvotes: 1

Views: 1447

Answers (3)

craigching
craigching

Reputation: 1963

You could introduce another element to your tuple such that you avoid comparing ListNode. For instance, you could do the following:

pq = PriorityQueue()
ln2 = ListNode(2)
ln = ListNode(1, ln2)
pq.put((ln.val, pq.qsize(), ln))
pq.put((ln2.val, pq.qsize(), ln2))

For PriorityQueue, qsize() is implemented as len(self.queue) where self.queue = []. This way you are guaranteed to have a unique value before your ListNode objects that is comparable. The only caveat is that qsize() will acquire a mutex before returning the size, so you do suffer that overhead.

Upvotes: 0

Hodja
Hodja

Reputation: 41

The PriorityQueue class sorts its objects as indicated by:

The lowest valued entries are retrieved first (the lowest valued entry is the one returned by sorted(list(entries))[0]).

When this is called on your objects that don't have an __lt__ method, it throws a TypeError.

To circumvent this, object IDs can be used instead of adding the object to the PriorityQueue. Python object IDs are globally unique, can can be obtained by calling id(object).

You can create a hashtable (dictionary) that has object ids as keys, and the object as the value.

pq = PriorityQueue()
list_node_A = ListNode(2)
list_node_B = ListNode(1)
for list_node in [list_node_A, list_node_B]:
    object_dictionary[id(list_node)] = list_node    # create id reference in dict
    pq.put((list_node.val, id(list_node))           # put into queue
list_node_id = pq.get()                             # get out of queue (id)
list_node = object_dictionary[list_node_id]         # get object from dict by id

Upvotes: 0

Bret Hogg
Bret Hogg

Reputation: 121

You should be able to use a tuple to put the priority and the object in the PriorityQueue. Try:

pq = PriorityQueue()
ln2 = ListNode(2)
ln = ListNode(1, ln2)
pq.put((ln.val, ln))
pq.put((ln2.val, ln2))

Upvotes: 2

Related Questions