On 9/9/10 12:09 PM, Phil Bewig wrote:
I did treaps, too: http://programmingpraxis.com/2009/06/26/treaps/. And I use them all the time, including where most people probably use hash tables, because so often you need the keys in order somewhere in your program.
I'm sorry, I shouldn't have said "no one"; I should have said "almost no one". I have seen references to it in various code bases. But it isn't the first thing that comes to most people's minds.
Your hints, and the solutions provided, use rotations, which is the way the original Aragon-Seidel paper presented the material. (Aragon and I were fellow grad students.) The split-join implementation of Blelloch and Reid-Miller [SPAA 1998] is better suited to a purely functional implementation and results in cleaner, shorter code -- simple enough that I can use it as enrichment material for a first-year class, and present it in a single tutorial session. --PR
_________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
