Updating a PriorityQueue

user_2359430 0
Viewed 161

I'm extremely confused about the different behavior of PriorityQueue when the item is an integer versus a string. But before addressing that, I'd like to understand the following behavior (using items as integers).

Suppose I have a priority queue with the following data (for each element, the first value is the priority and the second value is an item):

Image 1:

enter image description here

After I execute the following commands:

pq.put(pq.get())

The elements become sorted as follows:

Image 2:

enter image description here

Why have some elements changed places? What's going on with the sorting?

Here's the code to reproduce these screenshots from the debugger:

from sys import maxsize
from queue import PriorityQueue

items = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 17, 15, 16]
INFINITY = maxsize
minDist = {k: INFINITY for k in items}
minDist[3] = 0

pq = PriorityQueue(len(minDist))

for v in minDist.keys():
    pq.put([minDist[v], v])

# At this point, pq has the elements as shown in Image 1

pq.put(pq.get())

# Now, pq has elements scrambled as shown in Image 2

LESSONS LEARNED

Based on the investigations and discussions below, each call to pq.put(pq.get()) will rearrange the priority queue data structure. It's not clear if there's a way to control that. Please comment below if you know how!

My specific problem seems to be related to the sorting of items. As shown in Images 1 and 2, the items are integers from 1 to 17. If they're converted to strings (i.e., "1", "2", ..., "17"), I was getting a different behavior from the main function in my original code. However, if I use zfill(2) for each key, so that I have "01", "02", ..., "17", I'm able to get the same final results as what I get if I use integers instead.

priority-queue python-3.x python
1 Answers

It is not clear to me what is happening in the screenshots you show, but an example session with the interpreter is shown below that tries to recreate the problem with a slightly different approach:

Python 3.8.2 (tags/v3.8.2:7b3ab59, Feb 25 2020, 23:03:10) [MSC v.1916 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license()" for more information.
>>> import math, pprint, queue
>>> min_dist = {x: math.inf for x in range(1, 17)}
>>> min_dist[3] = 0
>>> pq = queue.PriorityQueue(len(min_dist))
>>> for key, value in min_dist.items():
    pq.put((value, key))


>>> pq_items = []
>>> while not pq.empty():
    pq_items.append(pq.get())


>>> pprint.pprint(pq_items)
[(0, 3),
 (inf, 1),
 (inf, 2),
 (inf, 4),
 (inf, 5),
 (inf, 6),
 (inf, 7),
 (inf, 8),
 (inf, 9),
 (inf, 10),
 (inf, 11),
 (inf, 12),
 (inf, 13),
 (inf, 14),
 (inf, 15),
 (inf, 16)]
>>> for key, value in min_dist.items():
    pq.put((value, key))


>>> pq.put(pq.get())
>>> pq_items.clear()
>>> while not pq.empty():
    pq_items.append(pq.get())


>>> pprint.pprint(pq_items)
[(0, 3),
 (inf, 1),
 (inf, 2),
 (inf, 4),
 (inf, 5),
 (inf, 6),
 (inf, 7),
 (inf, 8),
 (inf, 9),
 (inf, 10),
 (inf, 11),
 (inf, 12),
 (inf, 13),
 (inf, 14),
 (inf, 15),
 (inf, 16)]
>>>

You may want to adapt your code to use a similar approach to get what you are looking for. If you are having trouble with strings, then you may want to examine how your elements would be ordered if they were put into a list and then sorted.

user_2163560
Related