From oleg@pobox.com Thu Oct 8 12:27:31 1998
From: oleg@pobox.com
To: oleg@pobox.com
Subject: _Always_ efficient priority queues
Date: Thu, 08 Oct 1998 19:22:50 GMT
Reply-To: oleg@pobox.com
Keywords: treap, algorithm analysis, self-balanced tree, priority queue, Scheme
Newsgroups: comp.lang.scheme
NNTP-Posting-Host: 192.16.167.17
Organization: Deja News - The Leader in Internet Discussion
References: <874stlqfue.fsf@ivm.de>
Summary: discussing benefits of treaps as priority queues
X-Article-Creation-Date: Thu Oct 08 19:22:50 1998 GMT
X-Http-Proxy: 1.0 x3.dejanews.com:80 (Squid/1.1.22) for client 192.16.167.17
X-Http-User-Agent: Mozilla/4.06 (Macintosh; I; PPC, Nav)
Content-Length: 2235
Status: RO
A simple priority queue implementation posted here on Oct 4th by Phil
Bewig is neat, and will work great for small queues which are not
being frequently updated. An inefficiency is that it may take a linear
amount of time to insert a new element in a queue. For example,
consider inserting numbers 1, 2, 3, 4, 5 into an empty queue; or
evaluating (list->priqueue '(5 4 3 2 1)). The latter procedure's
algorithm in this unfortunate case becomes quadratic in time and
linear in stack space: neither list->priqueue or priqueue-merge are
tail-recursive. Phil Bewig's algorithm has an advantage that fetching
an element off the top of the queue is trivial (and constant in time
and space). The deletion of that element may degenerate into an O(n)
reshuffling: For example, consider deleting top elements from a queue
(list->priqueue '(6 5 4 7 3 8 2 9 1))
There are priority queue algorithms whose efficiency does not
degenerate in bad cases. For example, the algorithms based on
_self-balanced_ trees of different kinds, or a treap in
particular. Insertions in a trip run in O(log n) amortized time
regardless of the sequence the keys are inserted in. One disadvantage
of a treap is that looking up an element with the highest/lowest
"priority" takes O(log(n)) time; yet deleting that element takes
O(log(n)) times always. The treap has a special procedure to dequeue a
min/max element and return it. BTW, that procedure is properly
tail-recursive. All credit goes to R. Seidel and C. R. Aragon for
discovering this wonderful data structure, and Stefan Nilsson for
providing one implementation (which I carefully analyzed and
re-wrote).
The treap code can be used as it is as a priority queue. The
validation code vtreap.scm contains a few test cases that enqueue
numbers in sequence, out of sequence, and in a lexicographic order of
their ASCII representation. The treap code contains 240 lines of
comments.
The code is available from
http://pobox.com/~oleg/ftp/Scheme/index.html#treaps
I have tried to submit the code to many public archives (the
Scheme repository, schemers.org and SLIB) and haven't gotten any reply
. Thus my site appears to be the only place this treap code is
available from.
Oleg