Position of element in queue

[jonathan-s]

I'm curious if you have any ideas of the best way of finding the relative position of an element in the queue that you wrote here.

A naive way would be to use the function nlargest, iterate through that list and keep track of the position as you iterate through the list. This would be problematic if n items is big. Can you think of better approach?

[nvictus]

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.