Daniel Lemire's blog

, 5 min read

Stable Priority Queues?

8 thoughts on “Stable Priority Queues?”

  1. KWillets says:
    1. Thanks. I already link to this reference in my blog post. Do you think any of them is attractive as far as implementation goes?

      1. KWillets says:

        Apologies for not noticing that — I made a mental bookmark to look through these later, but I haven’t looked in depth. So far Eppstein’s idea seems fairly costly, but the Fagerberg modification of Bentley-Saxe looks interesting.

        1. KWillets says:

          Now that I’ve looked at Fagerburg, it doesn’t make sense — the binary representation of n does not match the bucket structure if one of the buckets has had all of its members deleted.

  2. Ben says:

    I haven’t looked at the links, so this might be redundant, but wouldn’t it work to have a priority queue of FIFO queues? All of the items in a particular FIFO queue would all have the same score. Of course there are lots of ways to implement a FIFO queue; pick your favorite.

    1. Do you have an implementation (anything would do: Python, Perl, Ruby, JavaScript)?

      1. Ben says:

        Sorry, the idea I posted doesn’t work at all. When inserting a value that’s equal to a value already in the priority queue, there’s no guarantee that you’d stumble across the existing value.

  3. KWillets says:

    One minor insight is that this looks a lot more like sorting than heapifying. For instance inserting the same value n times means that the entries either have to be sorted internally on insert (in some fully ordered structure like a BST), or they have to keep timestamp counters as you describe, so that they can be ordered on output.

    A hybrid strategy is to sort them partially by timestamp on insert (into separate subqueues for each time range, say) and store the remaining lower-order time bits with each entry. The subqueues can then be managed in a queue-of-queues. There are some possible benefits in that only the newest subqueue accepts inserts, although I can see some costs too :(.