1

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

Jack
  • 3,913
  • 8
  • 41
  • 66
  • +close, too localized: I don't think SO is the most appropriate venue to ask questions to a specific person. Try email or the project page's "discussion" instead. – Juliet May 09 '11 at 15:59
  • 1
    well, this is a general question actually. It is just about CHDataStructures, I can remove the first sentence just in case someone know the answer. If you think this is too specific to CHDataStructures, please see other questions about CHDataStructures, are they all too localized? – Jack May 09 '11 at 16:12

1 Answers1

3

(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:

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

Community
  • 1
  • 1
Quinn Taylor
  • 44,553
  • 16
  • 113
  • 131