Hash functions for priority queues
Miklós Ajtai, Michael L. Fredman, János Komlós · 1983
The complexity of priority queue operations is analyzed with respect to the cell probe computational model of A. Yao. A method utilizing families of hash functions is developed which permits priority queue operations to be implemented in constant worst case time provided that a size constraint is satisfied. The minimum necessary size of a family of hash functions for computing the rank function is estimated and contrasted with the minimum size required for perfect hashing.