A heap is the textbook solution, and is a good way to implement a priority queue in general - although it is not obvious to me how you ensure stability (I don't understand them particularly well). However, multiple linked lists will likely give better performance if the number of priorities is small, as (apparently) in the OP's case. Also, the worst case performance, which may be critical, is easily quantified.
Alex
Yes, I have now implemented the queue with multiple single linked lists; every event gets a 'next' index pointer, and a separate list is maintained for every priorty.
Inserting is simple, just add to the proper linked list, and dequeuing needs to check all the queues in priority order until a non-empty queue is found, and remove the entry from that queue.
Memory usage is 2 bytes for every queue (head and tail pointer), and 1 byte in every queue entry for the 'next' pointer. I could reduce those to 4 bits each, but this requires a lot of bit operation increasing code size quite a lot.
Thank you all for your comments and suggestions.
The easiest way to ensure stability (i.e., first-in-first-out for items with the same priority) is simply to attach a timestamp to each item, and make the timestamp part of the sort key. :) I can't think of any way to ensure stability without using a timestamp. And timestamps suddenly get messy (though not intractably so) if you need the queue to handle more than INT_MAX insertions.
And there's no mess with ensuring stability. I like the linked-list solution, too.
-Arthur
I thought about that and have been thinking of posting it, but I was assuming the original poster wished to have the order of items with equal priority preserved. For example, if you have the following items inserted in the following order:
first A, whose priority is 1 then B, priority 2 then C, priority 2 finally D, priority 1
then, as I understand it, the data structure should guarantee that (if you then dequeue them all) they come out in the order A, D, B, C and any other order would be incorrect.
I'm not sure that a heap has this property. I'm not saying that it doesn't; I'm just not sure. It may be possible to implement a "stable" heap (by analogy with stable sorts, for lack of a better term).
It then occurred to me that if a heap doesn't preserve the order of equal-priority items, you could perhaps get around this by defining the priority to be the original priority combined with a sequence number that is incremented every time something is inserted into the queue. This works great except that eventually the sequence number will overflow. There are tricks like resetting the sequence number when the queue is empty, but this won't work in all cases, and I can't think of a simple trick that will always work. (Which, again, doesn't mean it doesn't exist.)
- Logan
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.