On 29/10/05, Daniel Amelang <daniel.amelang / gmail.com> wrote:
> Cool Brian! So, from what I can tell, you're providing (or could provide)
> some of the same functionality as rbtree. How does your creation compare?
>
> Dan Amelang
>
>

Hello Dan,

I have not looked very deep into rbtree. Maybe it is possible to
implement a priority queue on top of rbtree. But generally it seems
inverse to a priority queue. It orders by key, while a priority queue
orders by priority (value in hash terms).

A priority queue offers another (not a real subset) set of functions
than an rbtree. The complexity of the operations available in both
datastructures differs.

From the rbtree homepage:

"... the complexity for insert, search and delete is O(log N) in
expected and worst case."

while the complexities for the interesting operations in this priority
queue implementation are

insert O(1)
delete O(1) average
delete_min O(log n) average
change priority O(1) average

These properties allow for example to create an O(m + n log n)
shortest path algorithm where m is the number of edges and n the
number of nodes in the graph.

So to summerize, theses datastructures are different and are usefull
for different algorithms.

best regards,

Brian
--
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/