Priority queue random access

Question

I have priority queue which sorts elements by some value(lets name it rating). I need to take elements from queue by rating. So i need to implement function queue_get(rating). This function also increases rating which is okay with priority heap.

But problem is that each level of the heap is not ordered by rating. Elements of each level only satisfy the heap property. So I could not surely return N-th element by rating.

Are there any implementations of priority queue with such functionality? Should I use another data structure?

Answer 1

The simplest solution is to use a binary search tree that is self-balancing, e.g. AVL tree, splay tree or red-black tree. It allows you to access elements by their key in O(log n) time and iterate through the objects in their order in O(log n + k) where k is the number of elements iterated.

Answer 2

A collection class will usually give you some Map which is based on an ordered key, such as java.util.TreeMap or C++ std::map. Using this you can retrieve items in sorted order - you may have to invert the order if the class gives you items in increasing order. If all you want to do is to read the top N items this should be enough for you.

If you want random access to the Nth highest item, this can be done by annotating a tree data structure with the number of items beneath each node, but I am not aware of a widely available class library that gives you this.

Come to think of it, if you just want to retrieve the N highest items in order, you can do this with a priority queue if you are prepared to remove the items as you read them out - and put them back again later if you need to restore the original contents.