# A Selectable Sloppy Heap
## 4 Conclusions
### Applications and Concluding Remarks  
1. The new data structure finds applications in settings with large dynamic sets where insertions and deletions need to be handled fast, and there is no need to be very precise with the ranks of the elements handled. One such application is _approximate sorting_. An array of \(n\) elements is said to be \(L\)-_sorted_ if for every \(i\in[n]\), we have \(|\mathtt{rank}(a_{i})-i|\leq L\); see also [39; 40]. As shown by the lower bound argument in the Appendix A, the selectable sloppy heap can be used to \(L\)-sort \(n\) elements in \(O(n\log\left(n/L\right))\) time. 2. As mentioned in the introduction, the selection problem, and computing the median in particular, are in close relation with the problem of finding the quantiles of a set. A typical use of the median relies on its property of being both larger or equal and smaller or equal than a constant fraction of the \(n\) elements. Following Yao [25], an element (think of a player, in the context of tournaments) is said to be \((i,j)\)_-mediocre_ if it is neither among the top \(i\) nor among the bottom \(j\) of a totally ordered set \(S\). As such, an element from the middle third quantile group of an \(n\)-element set is \((\lfloor n/3\rfloor,\lfloor n/3\rfloor)\)-mediocre; or simply _mediocre_, for short. Repeatedly returning a mediocre element in a dynamic setting (with an initially empty set) can thus be accomplished via the new data structure, by setting \(k=3\) and then repeatedly executing Delete 2 or Read 2, as needed, at a minimal (constant) query cost. Similarly, putting \(k=100\) sets up the data structure for dynamic percentile maintenance in \(O(1)\) time per operation; to the best of our knowledge, this outperforms previously available data structures with respect to this application; e.g., the soft heap data structure of Chazelle [35] only offers constant amortized time per operation. 3. This is a continuation of our earlier discussion in Section 1 on using BSTs in the context of dynamic selection taking into account the new data structure. Traditionally, search trees do not allow duplicate keys; it is however an easy matter to augment each node of such a tree with a _multiplicity_ attribute associated with each distinct key. In particular, the multiplicity attribute is taken into account when computing the size attribute of a node. Now having a balanced search tree on \(n\) items augmented as described, insertion, deletion, and search all take \(O(\log n)\) time. Our construction method can be used for any parameter \(k\), with \(2\leq k\leq n\). The data structure obtained in this way can be viewed as an _approximate search tree_. In particular, one can search for a given key and the approximate rank of a search key can be determined. To be precise, the following hold: (1) For every \(k\), with \(2\leq k\leq n\), an approximate search tree on \(n\) items (duplicate keys allowed) can be constructed in \(O(n\log k)\) time. (2) Search for a given key takes \(O(n/k+\log k)\) time per operation; its approximate rank, i.e., the quantile group to which it belongs (out of \(k\)), can be reported in \(O(\log k)\) time (regardless of the presence of the key!). (3) Insertion can be accommodated in \(O(\log k)\) time per operation. (4) Deletion of an unspecified key from a given quantile group (out of \(k\)) takes \(O(\log k)\) time; while deletion of a given key takes \(O(n/k+\log k)\) time. It is worth noting that the approximate search tree we just described appears competitive when \(k\) is small and the search function is infrequently used. Then insertion and deletion of an unspecified key from a given quantile group (out of \(k\)) takes \(O(\log k)\) time (the deleted element is revealed after the operation); e.g., if \(k=O(\log n)\), these operations take \(O(\log\log n)\) time.