in reply to Re: Judy arrays and Perl
in thread Judy arrays and Perl

i am already a data structures/algorithms obsessive

You too eh? My next target (ive got Trie's, Efficient Huffman Encoding, 2-3 trees, Pagoda Heaps under my belt so far) is a Treap. Any idea of a good place to look for documentation? Knuth only provided the most fleeting mention in AoP, and apparently they outperform splay trees and normal heap implementations (while being fully ordered) so I really want to release a CPAN implementation (especially as IMO the Heap:: heirarchy chews)

BTW thanks for the nod. :-)

Yves / DeMerphq
---
Writing a good benchmark isnt as easy as it might look.

Replies are listed 'Best First'.
Re(3): Judy arrays and Perl
by gumby (Scribe) on Jun 20, 2002 at 16:06 UTC
    My own reference for implementing a Treap was section 2 of this paper.

    A google search for Randomized Search Trees provided only a handful of relevant links. The entry in NIST DADS was pathetic, but provided a link to an implementation in Scheme.

[reply]
      Hmm. the paper link seemed to be to only an abstract... (did i miss a link?)

      Anyway I found this Animated Treap Example which looks fairly interesting. I also found these. When I get a chance i'll put together a perl implementation..

      Treap Explanation and Java Treap

      Yves / DeMerphq
      ---
      Writing a good benchmark isnt as easy as it might look.

[reply]
        ...you missed a link. On the top right hand corner of the page (under 'View or Download') there are links to download the full paper in PostScript, PDF and other file formats.
[reply]

In Section Meditations