Re: Skip Lists and Priority Queues?

Oliver Wong wrote
(in article <5f0Nf.7629$Cp4.2596@edtnps90>):

"Leslie Sanford" <jabberdabber@xxxxxxxxxxxxxxxxx> wrote in message
news:9eudnUdbPbaRFZnZRVn-iQ@xxxxxxxxxxxxxx
I was thinking about implementing a priority queue using a skip list. A
cursory examination makes me think that a skip list will perform well. For
one, dequeing(sp) simply requires removing the first node in the list and
updating the header. Inserting is comparable to inserting into a balanced
tree, I believe.

Would this be acceptable performance for a priority queue?

Part of my reason for wanting to use a skip list is that I'm familiar with
it having implemented skip lists in several languages.

Didn't know what a Skip List was, so I read your article on
codeproject.com, and it looks like a reasonable data structure, especially
with p = 1/2.

Didn't Pugh come up with them about 15 years ago? They looked
promising on paper, but in practice can be worse performers than
older data structures, such as various forms of balanced trees.
It's been at least a decade since I played with them, but they
did have some advantages with respect to memory consumption in
resource-constrained environments.


--
Randy Howard (2reply remove FOOBAR)
"The power of accurate observation is called cynicism by those
who have not got it." - George Bernard Shaw





.

Relevant Pages

  • Re: Why cons *pairs*?
    ... So why are lists used as the basis of program representation, ... a legal data structure isomorphic to the parse tree of the program, ... structures are most naturally expressed by that syntax?" ... CONS-based lists support these fairly well. ...
    (comp.lang.scheme)
  • Re: terminological obscurity
    ... anomolous why Guido didn't say what he meant himself. ... the distinction between homogenous data and a homogenous ... >> that at the Object level, we are at lists of Objects and tuples of ... >in Python but a recursive data structure. ...
    (comp.lang.python)
  • Re: How to count value in a ArrayList
    ... were adding was not already stored in the data structure. ... Doing this with a ArrayList is a lot slower than a hash ... But presumably they use a relatively common technique of having a fixed-sized array of bins that grows as the hash table accumulates items. ... Some implementations use bins that are either arrays or linked lists, while others simply use the next available spot in the hash table. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: [opensuse] Double Linked List patented in 2006
    ... You might want to read about "Skip Lists." ... but it is vaguely like the data structure ... to allow for fast concurrent access and update). ... faster than a heap-based priority queue. ...
    (SuSE)
  • Re: Missing Tomes of Data Structures
    ... source) for a deterministic skip lists. ... there is a data structure called a forward-balancing B- ... Tree that lets implementors lock sub-trees instead of the entire tree ... As far as the skip-list goes, as near as I can tell from the descriptions of the algorithm, randomization is a key element of the data structure. ...
    (microsoft.public.dotnet.languages.csharp)