Strictly implicit priority queues: on the number of moves and worst-case time

DOI10.1007/978-3-319-21840-3_8MaRDI QIDQ3449808zbMATH OpenOpenAlexFDO

Authors Gerth Stølting Brodal, Jesper Sindahl Nielsen, Jakob Truelsen

Publication date 30 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: The binary heap of Williams (1964) is a simple priority queue characterized by only storing an array containing the elements and the number of elements $n$ - here denoted a strictly implicit priority queue. We introduce two new strictly implicit priority queues. The first structure supports amortized $O(1)$ time Insert and $O(logn)$ time ExtractMin operations, where both operations require amortized $O(1)$ element moves. No previous implicit heap with $O(1)$ time Insert supports both operations with $O(1)$ moves. The second structure supports worst-case $O(1)$ time Insert and $O(logn)$ time (and moves) ExtractMin operations. Previous results were either amortized or needed $O(logn)$ bits of additional state information between operations.

Recommendations

• scientific article; zbMATH DE number 4062572
• Optimizing binary heaps
• Distribution-sensitive binomial queues.
• scientific article; zbMATH DE number 871899
• Algorithms and Data Structures

Cites work

• scientific article; zbMATH DE number 4062572 (Why is no real title available?)
• scientific article; zbMATH DE number 2119642 (Why is no real title available?)
• A survey on priority queues
• Efficient Algorithms for Shortest Paths in Sparse Networks
• Finger search in the implicit model
• Implicit dictionaries with O(1) modifications per update and fast search
• Linear-time in-place selection in less than 3n comparisons
• Sorting stably, in place, with \(O(n \log n)\) comparisons and \(O(n)\) moves
• Strictly implicit priority queues: on the number of moves and worst-case time
• Weak heaps engineered

Cited in

(6)

• Algorithms and Data Structures
• An in-place priority queue with \(O(1)\) time for push and \(\lg n + O(1)\) comparisons for pop
• Strictly implicit priority queues: on the number of moves and worst-case time
• Optimizing binary heaps
• Worst case constant time priority queue
• scientific article; zbMATH DE number 4062572 (Why is no real title available?)

This page was built for publication: Strictly implicit priority queues: on the number of moves and worst-case time

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