Dynamic ordered sets with approximate queries, approximate heaps and soft heaps

DOI10.4230/LIPICS.ICALP.2019.95MaRDI QIDQ5091256FDOQ5091256

Authors: Mikkel Thorup, Or Zamir, Uri Zwick 

Publication date: 21 July 2022

Recommendations

• The soft heap
• Soft heaps simplified
• Selection from heaps, row-sorted matrices, and \(X+Y\) using soft heaps
• A simpler implementation and analysis of Chazelle's soft heaps
• A selectable sloppy heap

zbMATH Keywords

lower boundsword RAMorder queries

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites Work

• Introduction to algorithms.
• Time-space trade-offs for predecessor search
• Surpassing the information theoretic bound with fusion trees
• Dynamic ordered sets with exponential search trees
• Deterministic sorting in O(nloglogn) time and linear space
• Optimal bounds for the predecessor problem and related problems
• A minimum spanning tree algorithm with inverse-Ackermann type complexity
• Sorting in linear time?
• Equivalence between priority queues and sorting
• The soft heap
• Expected linear time sorting for word size \(\Omega (\log ^{2} n \log\log n)\)
• Soft heaps simplified

Cited In (3)

• The soft heap
• Selection from heaps, row-sorted matrices, and \(X+Y\) using soft heaps
• Predecessor queries in dynamic integer sets

This page was built for publication: Dynamic ordered sets with approximate queries, approximate heaps and soft heaps

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