Hash functions for priority queues

M. Ajtai, M. Fredman, J. Komlós

Research output: Contribution to journalArticlepeer-review

33 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)217-225
Number of pages9
JournalInformation and Control
Issue number3
StatePublished - Dec 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Engineering(all)


Dive into the research topics of 'Hash functions for priority queues'. Together they form a unique fingerprint.

Cite this