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