A selectable sloppy heap

DOI10.3390/A12030058MaRDI QIDQ2312418zbMATH OpenOpenAlexWikidataFDO

Authors Adrian Dumitrescu

Publication date 8 July 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

\(i\)th order statisticapproximate selectiondynamic quantile maintenancemediocre elementonline algorithmtournament

Mathematics Subject Classification ID

Order statistics; empirical distribution functions (62G30) Data structures (68P05) Online algorithms; streaming algorithms (68W27)

Abstract: We study the selection problem, namely that of computing the $i$th order statistic of $n$ given elements. Here we offer a data structure called emph{selectable sloppy heap} handling a dynamic version in which upon request: (i)~a new element is inserted or (ii)~an element of a prescribed quantile group is deleted from the data structure. Each operation is executed in (ideal!) constant time---and is thus independent of $n$ (the number of elements stored in the data structure)---provided that the number of quantile groups is fixed. This is the first result of this kind accommodating both insertion and deletion in constant time. As such, our data structure outperforms the soft heap data structure of Chazelle (which only offers constant amortized complexity for a fixed error rate $0<varepsilonleq1/2$) in applications such as dynamic percentile maintenance. The design demonstrates how slowing down a certain computation can speed up the data structure.

Recommendations

• Soft heaps simplified
• The soft heap
• Dynamic range selection in linear space
• Sorting and selection on dynamic data
• An optimal algorithm for selection in a min-heap

Cites work

• A Counting Approach to Lower Bounds for Selection Problems
• A minimum spanning tree algorithm with inverse-Ackermann type complexity
• A New Lower Bound for the Set-Partitioning Problem
• A randomized linear-time algorithm to find minimum spanning trees
• A Unified Lower Bound for Selection and Set Partitioning Problems
• Average case selection
• Bounds for Selection
• Closing a long-standing complexity gap for selection: \(V _{3}(42) = 50\)
• Expected time bounds for selection
• Fast Deterministic Selection
• Finding the n-th largest element
• Finding the median
• scientific article; zbMATH DE number 1629859 (Why is no real title available?)
• scientific article; zbMATH DE number 3767009 (Why is no real title available?)
• scientific article; zbMATH DE number 3633709 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 3342853 (Why is no real title available?)
• Introduction to algorithms.
• Measures of Presortedness and Optimal Sorting Algorithms
• New upper bounds for selection
• On lower bounds for selecting the median
• On the Average-Case Complexity of Selecting the kth Best
• Optimal parallel selection has complexity O(log log N)
• Optimal selection and sorting via dynamic programming
• Probability and Computing
• Progress in selection
• Quake heaps: a simple alternative to Fibonacci heaps
• Select with groups of 3 or 4
• Selecting the Median
• Slowing down sorting networks to obtain faster sorting algorithms
• Sorting and selection with equality comparisons
• The soft heap
• Time bounds for selection

Cited in

(4)

• Self-Adjusting Heaps
• Dynamic ordered sets with approximate queries, approximate heaps and soft heaps
• Finding a mediocre player
• scientific article; zbMATH DE number 7765400 (Why is no real title available?)

Describes a project that uses

Uses Software

• Find
• MedianOfNinthers

This page was built for publication: A selectable sloppy heap

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