4

I am using 

from queue import PriorityQueue
pq = PriorityQueue()
pq.put((3, "Harry"))
pq.put((4, "Harry"))
pq.put((2, "Mary"))

This now creates two entries of "Harry". Am I supposed to remove all keys one by one (for searching) and then do a put to update the value?

martineau
  • 119,623
  • 25
  • 170
  • 301
dj014
  • 41
  • 1
  • 2
  • Which "Harry" do you want to update? They're already "sorted" by the order in which they were enqueued. – martineau Apr 26 '20 at 01:42
  • I actually only wanted to have one "Harry" in the priority queue whose priority I wanted to update from 3 to 4. The "put" function call creates two "Harry"s instead of updating the first "Harry". – dj014 Apr 26 '20 at 23:24
  • 3
    I don't think `PriorityQueue` supports deleting items or changing priorities. – martineau Apr 27 '20 at 00:20
  • 4
    By the way, unless you're using this queue specifically as a channel to send messages from producer threads to consumer threads, you should probably use `heapq` instead. The `queue` module is specifically intended for use as an inter-thread message passing system, and it has design choices and overhead that don't make sense for other uses. – user2357112 Apr 27 '20 at 01:34
  • https://stackoverflow.com/a/8706363/56778 explains how to delete in a heap. Neither Python's `PriorityQueue` nor `heapq` gives you the access to the backing array that is required to make this happen. – Jim Mischel Apr 28 '20 at 13:01
  • Can't you loop though the queue till you find the entry with "Harry", change its priority to a small number, add and then delete a bogus value, that way Harry will appear on the from of the queue and you can remove it with get. – edhu Apr 28 '23 at 01:48

2 Answers2

1

If you are okay with using a custom solution, here is a PriorityQueue that I implemented, and showcased with the Dijkstra algorithm: https://github.com/denizetkar/priority-queue

deniz
  • 167
  • 3
  • 9
0

The python documentation for PriorityQueue doesn't have a direct method to search a value inside Queue objects.

Edit: The PriorityQueue is implemented as a binary heap so changing the priority in the elements it won't update the binary tree as Jim Mischel said:

Changing the node's priority results in a potentially invalid heap.

Gober
  • 147
  • 2
  • 3
  • 12
  • Your code results in a `PriorityQueue` with the contents: `(1, 'Harry'), (2, 'Mary'), (3, 'Harry')` — so doesn't appear to work. – martineau Apr 26 '20 at 23:41
  • Another thing is that although the `queue` attribute isn't marked private, I don't think using it is part the public interface to a `PriorityQueue` (or regular `Queue` for that matter). – martineau Apr 27 '20 at 00:11
  • I didn't know that he only wanted unique values in the `PriorityQueue`, the code works only to change the priority of an item, using a `set` to be sure that there are unique elements it will be a better approach. – Gober Apr 27 '20 at 00:55
  • 1
    The code when I wrote my comment doesn't change the priority of an item. It also seems counterproductive to do a linear search, O(n), through a priority queue. – martineau Apr 27 '20 at 01:31
  • I changed the code with the new information, I agree with you about O(n) complexity, a better approach it will be to search using the iformation about the [binary heap](https://stackoverflow.com/a/25825860/8425653) – Gober Apr 27 '20 at 01:42
  • 1
    Your `change_priority_of' method won't work. If the node you changed the priority of is not on the same branch of the tree the new "Dummy" node is added to, then it won't be affected by adding and removing a node. Changing the node's priority results in a potentially invalid heap. Any further operations on that heap have the potential of breaking. – Jim Mischel Apr 27 '20 at 23:18
  • Your totally right, I have not seen the error with the heap, I will upload my answer. – Gober Apr 28 '20 at 00:50
  • 1
    https://stackoverflow.com/a/8706363/56778 explains how to delete in a heap. Neither Python's `PriorityQueue` nor `heapq` give you the access to the backing array that is required to make this happen. – Jim Mischel Apr 28 '20 at 12:59