Re: Skip Lists and Priority Queues?
- From: "Oliver Wong" <owong@xxxxxxxxxxxxxx>
- Date: Tue, 28 Feb 2006 18:02:41 GMT
"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.
Assuming you have a constant max level, dequeue from the head is O(1) and insertion is (on average) O(log(n)) (but O(n) in the worst case, if you get unlucky with the probabilities).
This is better than the traditional solution of a heap or balance tree, which have O(log(n)) for both insertion and dequeueing.
Just make sure you choose a max-level that is generally lower than the typical length of the list. For example, if your list typically contains 5 elements, it makes no sense to have 50 levels, and check through all of them.
I wonder if there might be a way to create a "balanced skip list", such that the nodes in the list dynamically adjust their heights as elements are inserted and removed.
- Oliver
.
- Follow-Ups:
- Re: Skip Lists and Priority Queues?
- From: Randy Howard
- Re: Skip Lists and Priority Queues?
- References:
- Skip Lists and Priority Queues?
- From: Leslie Sanford
- Skip Lists and Priority Queues?
- Prev by Date: Skip Lists and Priority Queues?
- Next by Date: Re: Skip Lists and Priority Queues?
- Previous by thread: Skip Lists and Priority Queues?
- Next by thread: Re: Skip Lists and Priority Queues?
- Index(es):
Relevant Pages
|
