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

DOI10.1007/978-3-319-21840-3_8zbMATH Open1444.68055arXiv1505.00147OpenAlexW1815165802MaRDI QIDQ3449808FDOQ3449808

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)

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.

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

Recommendations

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

Mathematics Subject Classification ID

Data structures (68P05)

Cites Work

• Efficient Algorithms for Shortest Paths in Sparse Networks
• Title not available (Why is that?)
• Weak heaps engineered
• Implicit dictionaries with O(1) modifications per update and fast search
• Title not available (Why is that?)
• Linear-time in-place selection in less than 3n comparisons
• A survey on priority queues
• 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
• Finger search in the implicit model

Cited In (6)

• 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
• Title not available (Why is that?)
• Algorithms and Data Structures

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)