In this chapter, we return to the problem of implementing an . The difference now is that we assume the elements stored in the are -bit integers. That is, we want to implement , , and where . It is not too hard to think of plenty of applications where the data--or at least the key that we use for sorting the data--is an integer.

We will discuss three data structures, each building on the ideas of the previous. The first structure, the performs all three operations in time. This is not very impressive, since any subset of has size , so that . All the other implementations discussed in this book perform all operations in time so they are all at least as fast as a .

The second structure, the , speeds up the search in a by using hashing. With this speedup, the operation runs in time. However, and operations in an still take time and the space used by an is .

The third data structure, the , uses an to store only a sample of roughly one out of every elements and stores the remaining elements in a standard structure. This trick reduces the running time of and to and decreases the space to .

The implementations used as examples in this chapter can store any type of data, as long as an integer can be associated with it. In the code samples, the variable is always the integer value associated with , and the method converts to its associated integer. In the text, however, we will simply treat as if it is an integer.