Hash functions for priority queues

The complexity of priority queue operations is analyzed with respect to the cell probe computational model of A. Yao (J. Assoc. Comput. Mach. 28, No. 3 (1981), 615–628). 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