Re: High-performance Priority Queue / Heap for glib

[Peter Clifton <pcjc2 cam ac uk>]

On Tue, 2009-03-10 at 20:53 +0100, Maik Zumstrull wrote:
> Maik Zumstrull wrote:
> 
> > Behdad Esfahbod wrote:
> 
> > > I agree that having a priority queue in glib would be useful.
> > > However, the API should use an opaque structure and be agnostic of
> > > the actual implementation.
> > 
> > I'm going to rethink the API and package the thing as a patch against
> > 2.19.10 sources. Maybe the discussion will pick up a little when
> > there's actual code on the table. Thanks for the feedback so far.
> 
> Okay, here it is. I haven't extensively tested this for correctness or
> performance yet, but it basically works. The API is documented and
> should allow different implementations, I think. It's similar to what I
> suggested before, but I dropped merge(). I'm not sure every kind of
> underlying implementation could provide that efficiently. Also,
> priority queues and single entries of priority queues are syntactically
> different types now, but in reality the same thing with my
> implementation.

Hi,

Forgive my ignorance if this is a fundamentally stupid question.. but
would it still be a priority queue if rather than assigning an integer
priority when adding an element, the queue was set up with a callback
function - such that the user's implementation can compare the priority
of two items in the queue?

I'm looking at implementing a computational geometry algorithm (based on
Bentley-Ottmann) (and I've not got much experience in that field). The
priority function required is the x-coordinate of some points, but with
a tie-break on the y-coordinate in the case where the x-coordinates
match.

Without constraining the bounds of my coordinates, or performing some
separate coordinate -> priority mapping step (hard, since new coords are
generated as the algorithm progresses), this doesn't seem to be possible
with your implementation.

Any thoughts?

Best regards,

Peter Clifton