Efficient priority list

Question

I am looking for an efficient data structure to represent a priority list. Specifically I need to assign a priority to a set of items and return only the top scoring items. I have looked into priority queues which operate on heaps, but they don't seem to really suit my needs. They will reorganize the heap structure as soon as I will poll the top rating item from the queue.

The simplest solution would of course be a linked list, which in the worst case would take quite long for the insertion operation.

Does anyone have a better solution?

Answer 1

Hmm. Skip lists? They should have O(log n) insertion (as heap-based queue) but getting top element should be O(1) [including removing it]. They could be even implemented using lock-free algorithm.

Answer 2

The JDK has a built-in pqueue class (java.util.PriorityQueue) which is based on a heap algorithm.

Sorry, I only just saw the bit about heaps not fitting your needs. Can you explain why? You can write a custom comparator (or make your items comparable) and the PriorityQueue will order your items appropriately.

Answer 3

If you need only the k top items and you never need to look a the others, you can use a simple linked list or array storing only the current top k items, plus a number (the worst score of the elements in the list).

In the Add() operation you simply compare the item with the worst value in the list and, if better, you swap the current worst with the added item. This takes O(k) time in the worst case for insertion because you need to find the element that has currently the worst score. The the average case, however, is O(1), since, as you add better elements to the list, the probability of having to do a swap tends to 0 (that is, you're not actually adding any items).

So if you generate elements at random, your performance is likely to be very good. Even if you generate ordered items (worst case), it might be fast enough for your value of k.

Answer 4

Heaps seem very suitable, and it seems like you are going about it wrongly.

Say you wanted the top x elements (how does this x compare to n, btw?)

What you are doing is putting all into a max-heap and getting the top x.

I suggest instead, you use a min-heap of exactly x elements.

First x elements you insert into heap.

Next incoming element, you compare against the min which can be done very quickly (O(1) time) in the heap. If smaller, you just ignore the incoming element.

If incoming element is larger than min, then you increase the min to the incoming element and sift it down in the heap. This should be logx time at worst.

Once done (in nlogx time), you can retrieve the elements from the heap in sorted order in O(xlogx) time.

Depending on how your data is (and how small x is), using this min-heap solution can be really fast.

---

If you really really want the inserts to be super-fast and don't care much about the retrieval then you can also do the following.

Insert the elements into a vector (array with amortized O(1) insert time) in the order they come.

The use the Selection algorithm to find the xth largest element (in O(n) time, but the constants might be big). Say that number is S.

Now walk the array comparing each element with S and select the ones as large as S.

If x is reasonably sized and comparable to n (like n/2 or something) this might work out fine, but if x is small compared to n, I would suggest go with the min-heap.