Equivalence between priority queues and sorting

DOI10.1145/1314690.1314692MaRDI QIDQ3546352zbMATH OpenOpenAlexWikidataFDO

Authors Mikkel Thorup

Publication date 21 December 2008

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1314690.1314692

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Equivalence between priority queues and sorting in external memory
• Priority Queues and Permutations
• scientific article; zbMATH DE number 2086621
• Priority queues
• Ordered priority queues
• Priority queues and multisets
• Priority queues with binary priorities
• Rank order filters and priority queues
• Priority queue sorting and labeled trees
• The permutational power of a priority queue

Cited in

(13)

• Dynamic coresets
• scientific article; zbMATH DE number 7561588 (Why is no real title available?)
• A simple reduction from maximum weight matching to maximum cardinality matching
• Linear-time approximation for maximum weight matching
• A forward-backward single-source shortest paths algorithm
• A scaling algorithm for maximum weight matching in bipartite graphs
• Priority queues and sorting for read-only data
• Rank order filters and priority queues
• Optimizing binary heaps
• A survey on priority queues
• Algorithms and Computation
• Equivalence between priority queues and sorting in external memory
• Multipartite priority queues

This page was built for publication: Equivalence between priority queues and sorting

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