Apparent error in Python's priority queue and heapq

After some time spent trying to find a rumored error in Python's priority queue (Queue.PriorityQueue), I have succeeded in writing a little program that can reproduce this error.

Code is available at https://bitbucket.org/dpb/queue_change_test . It is intended for Python v. 2.6. As I found recently, the problem does not normally arise when simple data structures are placed in the queue and can be sorted in lexicographic order; when stable sort is at issue, however, the queue sometimes fails.

The error occurs in this code when lists are enqueued and some of their values are then changed outside of the queue. The queue should automatically reorder itself, but this does not always happen correctly.

If, after the change to the values, the queue is emptied into another list and those contents then re-enqueued, the new queue is found to be sorted correctly. That shows that the problem has something to do with the queue data structure itself and not the values in the queue. The queue adds values correctly but does not always sort them correctly when they are changed after being added.

The pseudo-random numbers in the program use a seed, to allow the error to be reproduced.

The user has two options:

• to enter other seeds (default is none, in which case Python attempts to make the results look random by seeding with system time);
• to re-enqueue the contents, as described above, in order to eliminate sorting errors (default is not to re-enqueue).

[end]