Hash Functions for Priority Queues

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.

Authors

• Miklós Ajtai
• Michael L. Fredman
• János Komlós

Keywords

• Probes
• Queueing analysis
• Computational modeling
• Data structures
• Encoding
• Hash Function
• Priority Queue
• Data Structure
• Minimum Size
• Time Constant
• Memory Cells
• Complexity Measures
• Linear Space
• Family Of Subsets