StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>(Sorry, I just barely saw this question.)</p> <p>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.</p> <p>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.</p> <p>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.</p> <p><strong>Update:</strong> I found these related questions:</p> <ul> <li><a href="https://stackoverflow.com/questions/6909617/how-to-preserve-the-order-of-elements-of-the-same-priority-in-a-priority-queue-im">How to preserve the order of elements of the same priority in a priority queue implemented as binary heap?</a></li> <li><a href="https://stackoverflow.com/questions/5779849/priority-queue-c">Priority Queue C</a></li> <li><a href="https://stackoverflow.com/questions/2613994/priority-queue-implementation-in-c">Priority queue implementation in C</a></li> <li><a href="https://stackoverflow.com/questions/4231140/priority-queue-data-structure">priority queue data structure</a></li> <li><p><a href="https://stackoverflow.com/questions/2702913/implementing-java-priority-queue">Implementing Java Priority Queue</a></p></li> <li><p><a href="https://cstheory.stackexchange.com/questions/593/is-there-a-stable-heap">https://cstheory.stackexchange.com/questions/593/is-there-a-stable-heap</a></p></li> </ul> <p><a href="https://stackoverflow.com/questions/tagged/priority-queue">https://stackoverflow.com/questions/tagged/priority-queue</a></p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload