Hash functions for priority queues

DOI10.1016/S0019-9958(84)80015-7MaRDI QIDQ3719870zbMATH OpenOpenAlexDBLPWikidataFDO

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

Publication date 1984

Published in Information and Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0019-9958(84)80015-7

zbMATH Keywords

cell probe computational modelcomplexity of priority queue operationsdata structureperfect hashingrank function

Mathematics Subject Classification ID

Searching and sorting (68P10) Information storage and retrieval of data (68P20)

Recommendations

• On RAM Priority Queues
• Distribution-sensitive binomial queues.
• Worst-case efficient external-memory priority queues
• scientific article; zbMATH DE number 871899
• scientific article; zbMATH DE number 871900

Cited in

(11)

• A lower bound for finding predecessors in Yao's cell probe model
• Fusion trees can be implemented with AC^0 instructions only
• Surpassing the information theoretic bound with fusion trees
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths
• A constant update time finger search tree
• When can we sort in o(n n) time?
• Optimal bounds for the predecessor problem and related problems
• Last-come-first-served hashing
• Persistence, randomization and parallelization: On some combinatorial games and their applications (abstract)
• An algorithm for finding predecessors in integer sets
• On the cell probe complexity of polynomial evaluation

This page was built for publication: Hash functions for priority queues

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3719870)