Introduction > The Data Structure Interface Implementation Finishing Touches Conclusion

Treaps in Java The Data Structure The data structure consists of a balanced tree. Therefore, an element is never more than about lg n steps away, where n is the number of elements in the treap and lg n the binary logarithm (you may think of lg n as the number of bits needed to represent the number n in binary notation).      Being able to access the elements in the treap in lg n time is a big improvement over some of the most common basic data structures; see Table 1. Table 1: Worst-case time for some basic operations in some basic data structures.   Insert Find Min  Unsorted array 1 n n  Sorted array n log n 1  Unsorted linked list 1 n n  Sorted linked list n n 1  Hash table 1 1 n  Treap log n log n log n The treap is reasonably space efficient as well. Each element is stored in a node in a tree, and each node contains an integer and two references, one to the left subtree and one to the right subtree. Hence, to store n elements in a treap, we need n integers and 2n references. The standard hash-table implementation in java.util uses n integers for the hash values and n references for the linked lists. Furthermore, it uses an array with a size that is typically close to n. For example,with a load factor of 1.0, the hash table will use the same amount of extra space as a treap if the table is full and more space if it's only partly filled. One problem with the java.util hash-table implementation is that the array doesn't shrink. Even if you remove all but one of the elements, the size of the array is still proportional to the maximum number of elements that were stored in the table during its lifetime. The treap doesn't have this problem.

Dr. Dobb's Journal, July 1997