Re: Skip Lists and Priority Queues?


"Ben Pfaff" wrote:
"Leslie Sanford" writes:

Would this be acceptable performance for a priority queue?

There is at least one paper that compares the performance of 10
or so data structures for use in priority queues. Have you
looked for it and checked whether it covers skip lists?

I wasn't aware of the paper. Though searching for "priority queue data
structure comparison" led me to this:

"An empirical comparison of priority-queue and event-set
implementations"

http://portal.acm.org/citation.cfm?id=5686

Is this the paper you mean? It predates skip lists but looks interesting
nonetheless. Thanks.



.

Relevant Pages

  • Re: Skip Lists and Priority Queues?
    ... There is at least one paper that compares the performance of 10 ... or so data structures for use in priority queues. ... --Douglas Adams ...
    (comp.programming)
  • Re: Advice on data structure for scheduled events
    ... about using skip lists as priority queues awhile back: ... I have heard of skip lists, but know roughly nothing about them. ... the event and moving it further along in the list into one operation. ...
    (comp.programming)