Search code examples
pythonperformancesortingpriority-queue

Does PriorityQueue call sorted every time get is called?

The docs for queue.PriorityQueue say:

The lowest valued entries are retrieved first (the lowest valued entry is the one returned by sorted(list(entries))[0]).

Does that mean that every time I use the get method of a PriorityQueue that the elements are re-sorted? That would seem inefficient.

Solution

  • That does not means that the elements are re-sorted every time when you use the get method.

    The elements of a PriorityQueue are stored in a binary heap data structure, which allows for efficient retrieval of the smallest element when you call the method.

    So when sorting is done in such a way that the lowest valued elements are always at the top of the heap. That's why you will get smallest value on first.

    You can refer to example and Explanation in deeply