Re: Priority Queues


lauren wrote:
> What data structures other than Fibonacci heaps and queaps can handle
> constant time inserts and O(log N) extract min? I'm looking for one
> that's intuitive and easy to implement.

Thin heaps, fat heaps, relaxed heaps, and pairing heaps. Note that
for some of these extract-min is O(1) amortized, whereas for some
there are variants that are O(1) worst-case. Pairing heaps might be
the easiest to implement.

> If there isn't any such data
> structure, is it non-existant because it is non-trivial to conjure up
> one?

It's not for lack of effort.

.