Implicit data structures for the weighted dictionary problem
Greg N. Frederickson · 1981
Several new data structures are presented for dictionaries containing elements with different weights (access probabilities). The structures use just one location in addition to those required for the values of the elements, and support access times that are within a constant multiplicative factor of optimal, in terms of the rank of the weight of the desired element. Self-organizing heuristics are analyzed, in terms of both weights and "near-ranks" of weights. The benefits of additional space are investigated within the context of self-organization and unsuccessful search.