I need to frequently find the minimum value object in a set that's being continually updated. I need to have a priority queue type of functionality. What's the best algorithm or data structure to do this? I was thinking of having a sorted tree/heap, and every time the value of an object is updated, I can remove the object, and re-insert it into the tree/heap. Is there a better way to accomplish this?
11
-
What type are the values?David Eisenstat– David Eisenstat2014-03-28 19:41:22 +00:00Commented Mar 28, 2014 at 19:41
-
2How many items? What's the range of the values?David Eisenstat– David Eisenstat2014-03-28 19:44:48 +00:00Commented Mar 28, 2014 at 19:44
-
3@user3473949 Have you tried using buckets instead of a priority queue? I mean just storing for every value a linked list of items that have that value. Modify-key is then just a matter of removing the item from one list and adding it to another. If you keep a pointer to the minimum non-empty bucket you can find it in O(1). Maintaining that pointer when the bucket it points to gets empty might be slightly more costly, but it's just a linear scan over at most 100 pointers that easily fit into L1, so that's very cheap as well (and maybe the min doesn't change too often in your scenario)Niklas B.– Niklas B.2014-03-28 19:51:09 +00:00Commented Mar 28, 2014 at 19:51
-
1@NiklasB.: Delete-min can be sped-up by using a (bit-packed) vector of boolean values stating which buckets are non-empty, and quickly finding the least significant set bit in it.Gassa– Gassa2014-03-28 19:54:57 +00:00Commented Mar 28, 2014 at 19:54
-
1You say "being continually updated", but the kinds of updates matter enormously. Inserts? DeleteMins? Arbitrary deletes? Merge? DecreaseKey? IncreaseKey? Others?Chris Okasaki– Chris Okasaki2014-03-29 02:25:17 +00:00Commented Mar 29, 2014 at 2:25
|
Show 6 more comments
3 Answers
A binary heap is hard to beat for simplicity, but it has the disadvantage that decrease-key takes O(n) time. I know, the standard references say that it's O(log n), but first you have to find the item. That's O(n) for a standard binary heap.
By the way, if you do decide to use a binary heap, changing an item's priority doesn't require a remove and re-insert. You can change the item's priority in-place and then either bubble it up or sift it down as required.
If the performance of decrease-key is important, a good alternative is a pairing heap, which is theoretically slower than a Fibonacci heap, but is much easier to implement and in practice is faster than the Fibonacci heap due to lower constant factors. In practice, pairing heap compares favorably with binary heap, and outperforms binary heap if you do a lot of decrease-key operations.
You could also marry a binary heap and a dictionary or hash map, and keep the dictionary updated with the position of the item in the heap. This gives you faster decrease-key at the cost of more memory and increased constant factors for the other operations.
Comments
Quoting Wikipedia:
To improve performance, priority queues typically use a heap as their backbone, giving O(log n) performance for inserts and removals, and O(n) to build initially. Alternatively, when a self-balancing binary search tree is used, insertion and removal also take O(log n) time, although building trees from existing sequences of elements takes O(n log n) time; this is typical where one might already have access to these data structures, such as with third-party or standard libraries.
If you are looking for a better way, there must be something special about the objects in your priority queue. For example, if the keys are numbers from 1 to 10, a countsort-based approach may outperform the usual ones.
2 Comments
Niklas B.
Actually there are heaps with O(1) decrease-key (not sure about increase), but I guess those have constant factors that make them impractical
Gassa
@NiklasB.: Yeah, there are Fibonacci heaps for example, but from what I heard, they are impractical due to the large constant factor.
If your application looks anything like repeatedly choosing the next scheduled event in a discrete event simulation, you might consider the options listed in e.g. http://en.wikipedia.org/wiki/Discrete_event_simulation and http://www.acm-sigsim-mskr.org/Courseware/Fujimoto/Slides/FujimotoSlides-03-FutureEventList.pdf. The later summarizes results from different implementations in this domain, including many of the options considered in other comments and answers - and a search will find a number of papers in this area. Priority queue overhead really does make some difference in how many times real time you can get your simulation to run - and if you wish to simulate something that takes weeks of real time this can be important.
