Can I get an item from a PriorityQueue without removing it yet?

Question

I want to get the next item in queue but I don't want to dequeue it. Is it possible in Python's queue.PriorityQueue? From the docs, I don't see how can it be done

Forequarter

Answer 1

When you get item form the queue as per theory it will remove from the queue. You have to write your own function which will give you last element of PriorityQueue. You can create a peek function by inherit the priorityqueue.

Ostrich

Suppose I extend PriorityQueue, I still need to access the underlying data store to implement peak right? But how? – Forequarter

If you can check the code hg.python.org/cpython/file/2.7/Lib/Queue.py then they use list for storing the data. So you can play with the list as you want which is self.queue in the example. Also u can check the _get method of PriorityQueue so if you want to change that functionality then also override that function. – Ostrich

is cpython the same as python? – Forequarter

Answer 2

If a is a PriorityQueue object, You can use a.queue[0] to get the next item:

from queue import PriorityQueue

a = PriorityQueue()

a.put((10, "a"))
a.put((4, "b"))
a.put((3,"c"))

print(a.queue[0])
print(a.queue)
print(a.get())
print(a.queue)
print(a.get())
print(a.queue)

output is :

(3, 'c')
[(3, 'c'), (10, 'a'), (4, 'b')]
(3, 'c')
[(4, 'b'), (10, 'a')]
(4, 'b')
[(10, 'a')]

but be careful about multi thread access.

Refuse

And note that get() is blocking by default which indexing would not do. – Coy

In the case of multi threading, we could lock the q.mutex, and release the lock after reading q.queue[0]. – Isometry

It appears that while q.queue[0] returns the highest priority item in the queue, q.queue[1] does not necessarily return the 2nd highest priority item – Gunshy

@Woofas What you say is totally true and from my point of view, it's an unexpected behavior... Do you know why it happens? – Reine

@Reine I have no clue... I suppose it's doing some lazy evaluation to just keep the highest priority item on top without sorting the rest – Gunshy

@Woofas you will find that the 2nd highest priority is either q.queue[1] or q.queue[2]. That is because according to the theory of Priority Queues, the parent (q.queue[0] in this case) must have a higher priority that either of its two children (q.queue[1] and q.queue[2]), but the specific order of these two children is not important. This means that the whole q.queue is not absolutely sorted, only "heap" sorted (i.e every level has a higher priority than the level below it) – Buonarroti

why the example you have? It doesn't show what the OP is asking for – Angers

in terms of complexity, does a.queue[0] first construct the array and then return the first element? so O(n)? – Snaggy

@SobirBobiev No. Queue uses a.queue as its storage. The list is how the queue is stored in memory, in plain. As long as the queue is constructed, the list must there. By accessing the list directly you just circumvent the whole logic of the queue and go straight to its storage. – Chrystel

@SobirBobiev a.queue[0] is, thus, constant time. – Chrystel

"but be careful about multi thread access." -> Any idea how to solve multi thread access? – Stiltner

@Stiltner With multithreaded access, you can't assume that the top item will stay the top item, because other threads may manipulate the PriorityQueue. See my answer for an example: https://mcmap.net/q/326447/-can-i-get-an-item-from-a-priorityqueue-without-removing-it-yet – Kolo

Answer 3

If you want next element in the PriorityQueue, in the order of the insertion of the elements, use:

for i in range(len(queue.queue)):
    print queue.queue[i]

this will not pop anything out.

If you want it in the priority order, use:

for i in range(len(queue.queue)):
    temp = queue.get()
    queue.put(temp)
    print temp

If you are using a tuple, instead of a single variable, replace temp by:

((temp1,temp2))

Neglect

This solution isn't limited to just PriorityQueue objects. It also works for Queue objects. Seems like the most elegant solution to me. No offense intended, but I don't see how the other answers come close to this one (imho). – Damp

The first part does not give you the elements in the inserted order, but the first element will be the one with lowest value. – Alundum

Answer 4

Assuming your items stored in the PriorityQueue is a tuple (priority, value),

def peek(pq):
  return pq.queue[0][1] 

Ait

Answer 5

Indexing the first element of the queue should work. If you're using the heapq library, the document mentions:

The interesting property of a heap is that its smallest element is always the root, heap[0].

Library

Answer 6

If q is the PeriorityQueue, then you can use:

for i in range(q.qsize()):
    print(q.queue[i])

Gastrotrich

The answer to this question changes over the years as the implementation of PriorityQueue evolves. I verified that this still works in Python 3.11.7. Be aware that the above returns the tuple (priority, data), where data is either your wrapper class or the actual program object depending on which method you used to enqueue – Derian

Answer 7

TL;DR -- If you are are using the top item multiple times in a multithreaded environment, you should assign the item to a variable.

---

The above answers show how to access the elements of a PriorityQueue, however there is some danger when accessing objects from the inner queue in a multithreaded manner (as mentioned at the end of HYRY's answer).

While holding onto the queue object would be even less threadsafe, because that queue object is "live" (see this answer), you can still run into issues when accessing the objects on the queue if you expect the object ordering to be static.

Here's an example:

from queue import PriorityQueue          
import threading                         
import time                              
                                         
pq = PriorityQueue()                     
                                         
def queue_manip():                       
    i = 0                                
    while True:                          
        pq.put((i, i))                   
        i -= 1                           
        time.sleep(.1)                   
                                         
t1 = threading.Thread(target=queue_manip)
t1.start()                               
                                         
while True:                              
    print('FirstAccess:  ', pq.queue[0]) 
    time.sleep(.2)  # other processing   
    print('SecondAccess: ', pq.queue[0]) 
    time.sleep(.2)  # other processing   
    print()                              

which will print something like the below:

FirstAccess:   (0, 0)  
SecondAccess:  (-1, -1)
                       
FirstAccess:   (-3, -3)
SecondAccess:  (-5, -5)
                       
FirstAccess:   (-7, -7)
SecondAccess:  (-9, -9)

---

For this reason, if you want to use an object from the top of a PriorityQueue, you should assign that object to a name:

from queue import PriorityQueue          
import threading                         
import time                              
                                         
pq = PriorityQueue()                     
                                         
def queue_manip():                       
    i = 0                                
    while True:                          
        pq.put((i, i))                   
        i -= 1                           
        time.sleep(.1)                   
                                         
t1 = threading.Thread(target=queue_manip)
t1.start()                               
                 
while True:                           
    priority, item = pq.queue[0]      
    print('FirstUse:  ', item)        
    time.sleep(.2)  # other processing
    print('SecondUse: ', item)        
    time.sleep(.2)  # other processing
    print()                           
                                      

which will give you:

FirstUse:   0
SecondUse:  0

FirstUse:   -3
SecondUse:  -3

FirstUse:   -7
SecondUse:  -7

Kolo