How can I extract the minimum value of a PriorityQueue?

userNoIl1 0
Viewed 36

For example, I am working in a Dijkstra's code for my studies. So I was working with priority queues, however, I never used them before and I do not know how to extract the minimum value of the priority queue. Can someone help me?

Q = PriorityQueue()
Q.put((start, dist[start]))

while Q != 0:
     
  u = #the minimum value of PriorityQueue
priority-queue queue dijkstra algorithm
1 Answers

That will be up to the library that you are using.

For example in Python the most common library to use is heapq. It literally just gives a bunch of static methods to call on an array. So you get the interface:

import heapq

q = [...] # (priority, value) pairs
heapq.heapify(q)
...
heapq.heappush((some_priority, some_value))
...
while 0 < len(q):
    priority, element = heapq.heappop()
    ...

If this interface seems clumsy to you, it has seemed so to me for years. But heapq is in the standard library, and using it is easier than writing a better implementation. So I just use it.

If you want something more sophisticated, it isn't hard to write. But the sophistication will come with an abstraction somewhere, which will make it slower in practice. Given that people use priority queues for performance, pretty code might not be the win either of us would hope.

Other languages, of course, are different. For example here is PriorityQueue in Java.

btilly0
Related