Python, find element in PriorityQueue by value

Question

The priority queue PQ stores pairs

(weight, element),

sorted according to the weight. Does Python's implementation support the search operation in PQ by the element value (element in PQ or not)?

PQ = queue.PriorityQueue()
PQ.put((1,2))
PQ.put((5,6))
val = 6
print (val in PQ.queue)       #Nothing has been found

I suppose that items in PQ are stored in PQ.queue as tupples.

Thanks for your help.

Do you want to search for tuple like (5,6) or just 6 ?

Lakshya Srivastava
– Lakshya Srivastava

2019-05-02 18:26:59 +00:00
Commented May 2, 2019 at 18:26 — Lakshya Srivastava
– Lakshya Srivastava, Commented May 2, 2019 at 18:26

Lakshya Srivastava · Accepted Answer · 2019-05-02 18:33:46Z

1

Try this,

If you want to search for an element:

import queue

PQ = queue.PriorityQueue()
PQ.put((1, 2))
PQ.put((5, 6))
val =  4

while not PQ.empty():
   if val in PQ.get():
     print(True)

If you want to search for a tuple:

import queue

PQ = queue.PriorityQueue()
PQ.put((1, 2))
PQ.put((5, 6))
val = (5, 6)

while not PQ.empty():
  if val == PQ.get():
     print(True)

answered May 2, 2019 at 18:33

Lakshya Srivastava

7099 silver badges22 bronze badges

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

5 Comments

justik Over a year ago

@ Lakshya: Thanks for your samples. Hence, it is impossible to detect whether PQ contains an element without popping all elements in PQ.

Lakshya Srivastava Over a year ago

@justik, that's another question.

justik Over a year ago

@ Lakshya: Yes, it is, you are right. However, it is common to check the size of the dynamic structure without removing its content.

Lakshya Srivastava Over a year ago

you could use custom pqueue or heap or maintain a set for reconstruction with huge tradeoff.

justik Over a year ago

I tried also heapq, but I am not sure, if it supports any search by element operation.

ztf · Accepted Answer · 2023-08-14 12:56:25Z

I had the same problem when I tried to write a best-frist-search algorithm and ended up the following solution.

from queue import PriorityQueue

def contains_in_pq(pq, node):
    for item in pq.queue:
        if item[1] == node:
            return True
    return False
    
nodes = PriorityQueue()

#Put tuples of (priority and node id) into the p riority queue
nodes.put((99, 1))
nodes.put((98, 2))
nodes.put((96, 3))
nodes.put((100, 4))

print(contains_in_pq(nodes, 1))
print(contains_in_pq(nodes, 4))
print(contains_in_pq(nodes, 4))
print(contains_in_pq(nodes, 0))

while nodes.empty() == False:
    print(nodes.get()[1])

print(contains_in_pq(nodes, 4))


#Outputs:
# True
# True
# True
# False
# 3
# 2
# 1
# 4
# False

Collectives™ on Stack Overflow

Python, find element in PriorityQueue by value

2 Answers 2

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related