Worst-case optimal priority queues via extended regular counters

DOI10.1007/978-3-642-30642-6_13zbMATH Open1360.68380arXiv1112.0993OpenAlexW1599550474MaRDI QIDQ2907494FDOQ2907494

Authors: Amr Elmasry, Jyrki Katajainen 

Publication date: 10 September 2012

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Abstract: We consider the classical problem of representing a collection of priority queues under the operations Findmin{}, Insert{}, Decrease{}, Meld{}, Delete{}, and Deletemin{}. In the comparison-based model, if the first four operations are to be supported in constant time, the last two operations must take at least logarithmic time. Brodal showed that his worst-case efficient priority queues achieve these worst-case bounds. Unfortunately, this data structure is involved and the time bounds hide large constants. We describe a new variant of the worst-case efficient priority queues that relies on extended regular counters and provides the same asymptotic time and space bounds as the original. Due to the conceptual separation of the operations on regular counters and all other operations, our data structure is simpler and easier to describe and understand. Also, the constants in the time and space bounds are smaller. In addition, we give an implementation of our structure on a pointer machine. For our pointer-machine implementation, Decrease{} and Meld{} are asymptotically slower and require $O(lglgn)$ worst-case time, where $n$ denotes the number of elements stored in the resulting priority queue.

Full work available at URL: https://arxiv.org/abs/1112.0993

Recommendations

• scientific article; zbMATH DE number 871899
• Publication:4490355
• Worst case constant time priority queue
• Fast meldable priority queues
• Fat heaps without regular counters

Mathematics Subject Classification ID

Data structures (68P05)

Cites Work

• Fibonacci heaps and their uses in improved network optimization algorithms
• A data structure for manipulating priority queues
• Multipartite priority queues
• Fast meldable priority queues
• Two-tier relaxed heaps
• Title not available (Why is that?)
• Meldable heaps and boolean union-find
• Worst-case optimal priority queues via extended regular counters
• Strictly-regular number system and data structures
• Fat heaps without regular counters

Cited In (9)

• Fat heaps without regular counters
• Strictly-regular number system and data structures
• Regular numeral systems for data structures
• Bipartite binomial heaps
• Fat heaps without regular counters
• Worst-case optimal priority queues via extended regular counters
• A priority queue with the time-finger property
• Worst case constant time priority queue
• A survey on priority queues

This page was built for publication: Worst-case optimal priority queues via extended regular counters

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