Skip Lists and Priority Queues?

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.


.

Relevant Pages

  • Re: data structures module
    ... I wanted a priority queue. ... >>I notice that Python does not have any sorted lists. ... I like the general direction this is going - no new basic data types. ... Lists and dicts are sufficient for 98% of all will we ever need. ...
    (comp.lang.python)
  • 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: [opensuse] Double Linked List patented in 2006
    ... You might want to read about "Skip Lists." ... I thought about that as well, but skip lists are single linked lists, ... faster than a heap-based priority queue. ... in code footprint than any balanced tree algorithm I've seen so far - ...
    (SuSE)
  • Re: Ranking
    ... If your list has a total of N items, finding the top k in this list is Ousing a hash table, Ofor a sorted list, Ofor an unsorted list, and Ofor a priority queue. ... If the ratio of modifications to generations is m, then the total time is Ofor hash table, Ofor sorted lists, Ofor unsorted lists, and O*lg N) for priority queues. ... I am also assuming that a custom heap is used for the priority queue case to take advantage of the hash table. ...
    (comp.lang.java.programmer)
  • Re: problem with lists with customized permissions and broken inherance
    ... with the permissons inherance broken and with customized permissions. ... The lists are populated with about 2000 elements each one. ... After inserting, all seems to be rigth: ... SPRoleAssignment RoleAssignment = new ...
    (microsoft.public.sharepoint.windowsservices)