CHDataStructures: Priority Queue?

I need a priority queue, I开发者_运维百科 guess in the framework, CHMutableArrayHeap and CHBinaryHeap can do the job, right?

However, if i send objects with identical priority to the queue, both CHMutableArrayHeap and CHBinaryHeap cannot maintain their adding orders.

for example, I have objects obj1 to obj10, their priorities are identical. After I add those 10 objects to the queue one by one from 1 to 10, the positions of them are not the same as the adding order, obj4 may come in front of obj1.

So, Quinn, what do you suggest if I want a priority queue keeping the adding order if priority is the same?

Thanks

(Sorry, I just barely saw this question.)

The nature of a heap is that it doesn't preserve insertion order at all, so you'd have to (1) build a priority queue atop another data structure or (2) supplement the heap with another data structure that tracks insertion order. However, a heap is generally the most efficient (and preferred) way to implement a priority queue, so I don't know if it's a good idea to use something else. The main reason I say this is that you want insertion to be extremely fast, which a heap provides; adding to a sorted array doesn't.

One possibility is to maintain a queue (e.g. CHCircularBufferQueue) for each priority level. (I'd imagine you'd want to create a wrapper structure that managed the queues so callers don't have to deal with them directly.) You could potentially store the queues in a dictionary keyed by an NSNumber containing the priority, but I have no clue what the performance would look like. This obviously wouldn't scale very efficiently to extremely wide ranges of priorities, and might not for lots of inserts and removes, but it might be workable in small cases. Just an idea.

Another idea is to make a wrapper class that stores both priority and insertion time, then compares them in order. In this case, you'd probably want to use a sorted set (e.g. binary tree) to store them. However, the added overhead means you won't get the same performance as with a heap, but I suppose that's the tradeoff for maintaining insertion order.

Update: I found these related questions:

• How to preserve the order of elements of the same priority in a priority queue implemented as binary heap?
• Priority Queue C
• Priority queue implementation in C
• priority queue data structure

• Implementing Java Priority Queue

• https://cstheory.stackexchange.com/questions/593/is-there-a-stable-heap

https://stackoverflow.com/questions/tagged/priority-queue