Position of element in queue about pqdict HOT 1 OPEN

By finding the relative position, I'm taking that to mean finding the rank of an element among all other elements in the queue. That's an interesting problem!

Because it's implemented as a heap, the most naive solution would be to enumerate and pop elements out of the heap until we run into the key we are looking for. Basically, something equivalent to:

rank = next(dropwhile(lambda x: x[1] != key, enumerate(pq.copy().popkeys())))[0]

Since that operation is destructive, we make a copy of the queue first. Copying aside, as described in this blog post, should be O(k log(n)), where k is the rank of the element.

I'm not sure if using nlargest or nsmallest as you suggested would help in general, because you would need to know that the rank of your element is less than some k'. Otherwise, you might as well just sort all of the items and use classic bisection search. But if you do have an upper bound on the rank, I think it would end up being O(n log(k')), because those operations make a new heap of size k' and feed all n items through it.

However, the author of the blog post above also describes a non-destructive heap-rank algorithm, which is done by a simple traversal and brings the complexity down to O(k). That could make a nice rank() method to add to PQDict! As a bonus, the same algorithm also produces a "top-k set" of elements, because it traverses all elements of higher priority than the target one (though not in a sorted order).

Though, ultimately, if performing this kind of operation frequently is really important, it might make more sense to use a data structure backed by a fully sorted list rather than a heap. I believe the ValueSortedDict from sortedcollections is such an implementation.

from pqdict.