Hash functions for priority queues

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

doi:10.1016/S0019-9958(84)80015-7

Hash functions for priority queues

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

Research output: Contribution to journal › Article › peer-review

33 Scopus citations

Abstract

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 language	English (US)
Pages (from-to)	217-225
Number of pages	9
Journal	Information and Control
Volume	63
Issue number	3
DOIs	https://doi.org/10.1016/S0019-9958(84)80015-7
State	Published - Dec 1984
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Engineering

Access to Document

10.1016/S0019-9958(84)80015-7

Cite this

@article{9ea4e89894a44f61970e710b4945b17e,

title = "Hash functions for priority queues",

abstract = "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.",

author = "M. Ajtai and M. Fredman and J. Koml{\'o}s",

note = "Funding Information: in part by the National Science Foundation Grant MCS-8204031.",

year = "1984",

month = dec,

doi = "10.1016/S0019-9958(84)80015-7",

language = "English (US)",

volume = "63",

pages = "217--225",

journal = "Information and Control",

issn = "0019-9958",

publisher = "Elsevier Inc.",

number = "3",

}

TY - JOUR

T1 - Hash functions for priority queues

AU - Ajtai, M.

AU - Fredman, M.

AU - Komlós, J.

N1 - Funding Information: in part by the National Science Foundation Grant MCS-8204031.

PY - 1984/12

Y1 - 1984/12

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0021696375&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0021696375&partnerID=8YFLogxK

U2 - 10.1016/S0019-9958(84)80015-7

DO - 10.1016/S0019-9958(84)80015-7

M3 - Article

AN - SCOPUS:0021696375

SN - 0019-9958

VL - 63

SP - 217

EP - 225

JO - Information and Control

JF - Information and Control

IS - 3

ER -

Hash functions for priority queues

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this