Adding a custom object to a Priority queue in Python

Question

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.

are you solving a leetcode question? I remember this same class from one of the questions.. — gsb22
– gsb22, Commented Sep 29, 2021 at 16:40
the way I did is use a global counter and on every heappush i was using heapq, I insert the counter value as well. — gsb22
– gsb22, Commented Sep 29, 2021 at 16:41

Bret Hogg · Accepted Answer · 2021-09-29 06:57:25Z

2

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

answered Sep 29, 2021 at 6:57

Bret Hogg

1212 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Becay Over a year ago

I get the error: TypeError: '<' not supported between instances of 'ListNode' and 'ListNode'. But I am not allowed to temper with the ListNode class such that I can add the __lt__ method.

Bret Hogg Over a year ago

Hmm, it shouldn't be comparing ListNodes, but the int values. What does your code look like? Is the tuple in the correct order?

Becay Over a year ago

The problem occurs when I add a node whose value already exists in the priority queue. So it attempts to compare using the second element in the tuple. However, I want it to just add the new node (whose value is already in the queue) without worrying about the order relative to the other node with the same value.

Bret Hogg Over a year ago

So you can't temper with ListNode, can you temper with Priority Queue or create your own PQ implementation? Alternatively you could use 3 values for the tuple (value, value2, ln) where value2 is some int that differentiates list nodes with equal values. But you will run into the same issue if value2 is the same as some other.

Becay Over a year ago

The alternative with 3 values works well. I wish the built-in PriorityQueue would allow a comparison function as one of its arguments.

Hodja · Accepted Answer · 2022-08-02 09:38:06Z

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

craigching · Accepted Answer · 2022-08-18 16:05:21Z

0

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.

answered Aug 18, 2022 at 16:05

craigching

2,0033 gold badges15 silver badges12 bronze badges

Collectives™ on Stack Overflow

Adding a custom object to a Priority queue in Python

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related