A priority queue in which initialization and queue operations takeO(loglogD) time

DOI10.1007/BF01786986zbMath0522.68039OpenAlexW1977421134WikidataQ56078244 ScholiaQ56078244MaRDI QIDQ3673101

Donald B. Johnson

Publication date: 1982

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01786986

zbMATH Keywords

binary treepriority queuetime complexitydata structure

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Data structures (68P05)

Related Items (27)

On building the transitive reduction of a two-dimensional poset ⋮ Two- and three- dimensional point location in rectangular subdivisions ⋮ Sorting helps for Voronoi diagrams ⋮ Scanline algorithms on a grid ⋮ The k most vital arcs in the shortest path problem ⋮ Routing a vehicle of capacity greater than one ⋮ Computing the agreement of trees with bounded degrees ⋮ Bounded ordered dictionaries in O(log log N) time and O(n) space ⋮ EFFICIENT ALGORITHMS FOR (δ,γ,α) AND (δ, k_Δ, α)-MATCHING ⋮ On graphs preserving rectilinear shortest paths in the presence of obstacles ⋮ A double scaling algorithm for the constrained maximum flow problem ⋮ New clique and independent set algorithms for circle graphs ⋮ Dynamic programming with convexity, concavity and sparsity ⋮ Output-sensitive generation of the perspective view of isothetic parallelepipeds ⋮ Range-restricted mergeable priority queues ⋮ Fast local searches and updates in bounded universes ⋮ A faster polynomial algorithm for the constrained maximum flow problem ⋮ Output-sensitive generation of the perspective view of isothetic parallelepipeds ⋮ Biased predecessor search ⋮ Sorting by bounded block-moves ⋮ Finding the k Shortest Paths ⋮ Log-logarithmic worst-case range queries are possible in space theta(N) ⋮ A History of Distribution-Sensitive Data Structures ⋮ Chaining algorithms for multiple genome comparison ⋮ An O(m log log D) algorithm for shortest paths ⋮ New trie data structures which support very fast search operations ⋮ Compact recognizers of episode sequences

Cites Work

• Unnamed Item
• Unnamed Item
• Priority queues with update and finding minimum spanning trees
• Preserving order in a forest in less than logarithmic time and linear space
• Analysis of an algorithm for priority queue administration
• Efficient Algorithms for Shortest Paths in Sparse Networks
• Design and implementation of an efficient priority queue
• Implementation and Analysis of Binomial Queue Algorithms

This page was built for publication: A priority queue in which initialization and queue operations takeO(loglogD) time