|
Treaps
in Java
Stefan Nilsson
If you could use only one data structure, which one would you choose? A hash table?
While it supports the basic insert, find, and remove operations, it doesn't keep
the elements in sorted order. Therefore, it can't efficiently perform some tasks
that are frequently encountered, such as finding the minimum element or producing
an ordered list of all elements. The standard Java packages don't contain a data
structure for ordered data.
What would you require of this ideal, sole structure?
It should be easy to use (and preferably easy to implement); it should be able to
hold an object of any class (as long as you provide a method for comparing objects);
it should be efficient in terms of both speed and memory; and it should be thread
safe.
The randomized search tree ("treap"), devised
by C. R. Aragon and R. Seidel and described in "Randomized Search
Trees" (Algorithmica, 16(4/5):464-497, 1996), fulfills all of these
requirements, and it offers the functionality of a general-purpose sorting routine,
priority queue, hash table, stack, or standard queue.
Stefan is
a lecturer in the department of Computer Science at the Helsinki University of Technology.
He is doing research in the area of algorithms and data structures. Stefan can be
contacted at Stefan.Nilsson@hut.fi.
|
