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

DOI10.4230/LIPICS.ICALP.2019.95MaRDI QIDQ5091256zbMATH OpenFDO

Authors Mikkel Thorup, Or Zamir, Uri Zwick

Publication date 21 July 2022

zbMATH Keywords

lower boundsword RAMorder queries

Mathematics Subject Classification ID

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

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

Cites work

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

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)