Thanks. I already link to this reference in my blog post. Do you think any of them is attractive as far as implementation goes?
KWilletssays:
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.
KWilletssays:
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.
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.
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.
KWilletssays:
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 :(.
There are some options discussed here: http://cstheory.stackexchange.com/questions/593/is-there-a-stable-heap .
Thanks. I already link to this reference in my blog post. Do you think any of them is attractive as far as implementation goes?
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.
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.
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.
Do you have an implementation (anything would do: Python, Perl, Ruby, JavaScript)?
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.
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 :(.