## 1. Introduction

**Quantiles.**The kth quantiles of an n-element set are the $k-1$ order statistics that divide the sorted set in k equal-sized groups (to within 1). It is known that the kth quantiles of a set can be computed by a recursive algorithm running in $O(nlogk)$ time ([6], p. 223). Such an algorithm can be modified, if needed, so that the k groups can be also output, say, each as a linked list, within the same overall time. For $2\le i\le k-1$, the ith group of elements (bounded by the $(i-1)$th and the ith quantile) is referred to as the ith quantile group; the first quantile group consists of the elements less than or equal to the first quantile, and the kth quantile group consists of the elements greater than or equal to the $(k-1)$th quantile.

A “very sloppy heap” (abbreviated vsh) is a data structure for performing the following operations on a set S: (i) insert and (ii) delete-small. The latter operation deletes (and returns) an element x which is among the $\lceil n/2\rceil $ smallest elements in the set, where n is the current size of the set. Explain how to implement a vsh in constant amortized time per operation.

**Theorem**

**1.**

**Background and related problems.**Since the selection problem is of primary importance, the interest in selection algorithms has remained high ever since; see for instance [2,5,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24]. In particular, determining the comparison complexity for computing various order statistics including the median has led to many exciting questions, some of which are still unanswered today; in this respect, Yao’s hypothesis on selection ([25], Ch. 4) remains an inspiring endeavor [4,15,23]. A comprehensive review of early developments in selection is provided by Knuth [26]. Computational results on the exact comparison complexity of finding the ith smallest out of n for small $i,n$, have been obtained in [18,27]. We also refer the reader to the dedicated book chapters on selection in [6,7,28,29,30] and the more recent articles [9,31,32], including experimental work [33].

`Insert`,

`Delete-Min`,

`Decrease-Key`(and perhaps also

`Find-Min`,

`Increase-Key`, or other operations). See for instance [34] and the references therein for some new variants and recent developments.

`Create`and

`Meld`, the data structure accommodates

`Insert`,

`Delete`and

`Findmin`(

`Delete`x removes item x). Consider a sequence of $m\ge n$ operations after its creation, that includes n

`Insert`operations. For any $0<\epsilon \le 1/2$, a soft heap with error rate $\epsilon $ supports each operation in constant amortized time, except for

`Insert`which takes $O(log1/\epsilon )$ amortized time. The data structure ensures that at most $\epsilon n$ of its items are corrupted (their keys have been artificially raised).

`Findmin`returns the minimum current key (which might be corrupted). In contrast, our data structure uses $O(log1/\epsilon )$ time per operation, where $\epsilon \sim 1/k$, and thereby outperforms the soft heap with respect to the worst-case time per update (insert or delete) operation.

**Definition**

**1.**

- (a)
- Insertx: a new elementxis inserted.
- (b)
- Deletei: this deletes (and returns) some unspecified elementxwhich belongs to theith quantile group of the current set, where$1\le i\le k$; if$n<k$, the deleted element is not subject to any requirement.

**Outline of the paper.**To explain the main challenges and introduce the main ideas, we first sketch several preliminary implementations of the data structure, meeting suboptimal (in k) benchmarks: (i) $O(klogk)$ amortized time per operation for the first variant in Section 2; (ii) $O(klogk)$ worst-case time per operation for the second variant in Section 2; (iii) $O(logk)$ amortized time per operation for the third variant in Section 2. We then further refine these methods in Section 3 to obtain an optimal implementation of the data structure running in $O(logk)$ worst-case time per operation. In particular, for constant k, the second variant in Section 2 and the (main) variant in Section 3 run in $O(1)$ worst-case time per operation. We conclude in Section 4 with applications and some remarks.

**Comments and notations.**Duplicate elements are easily handled by the design. Each operation request is associated with a discrete time step, i.e., the jth operation occurs during the jth time step, where $j=1,2,\dots $ Without affecting the results, the floor and ceiling functions are omitted in the descriptions of the algorithms and their analyses.

## 2. Some Ideas and Preliminary Suboptimal Solutions

**A first variant with**$O(klogk)$

**amortized time per operation.**Let n denote the current number of elements in the data structure, with the elements being stored in a linear list (or an array). By default (if n is large enough) the algorithm proceeds in phases.

**A second variant with**$O(klogk)$

**worst-case time per operation.**The above idea is next refined so as to obtain the above expression as a worst-case time bound per operation. However, we need a larger set of quantiles: $9k$ buckets will suffice (a more detailed analysis likely gives a better bound). We can assume that $n\ge 9k$. The algorithm proceeds in phases: Each phase starts with a reorganization, namely computing the $(9k)$th quantiles and the corresponding quantile groups in time $O(nlog(9k))=O(nlogk)$. For Insert, add the new element to an initially empty overflow bucket (an empty overflow bucket is created at each reorganization). For Delete i, remove any element from the bucket $9i-4$, i.e., from the middle fifth of the ith quantile group (out of the total k).

**A third variant with**$O(logk)$

**amortized time per operation.**We briefly describe an implementation achieving $O(logk)$ amortized time per operation that is tailored on the idea of a B-tree; this variant was suggested by Fredman [36]. Use a balanced binary search tree $\mathcal{A}$ with $\mathsf{\Theta}(logk)$ levels storing $O(k)$ splitting keys at the leafs. Each leaf comprises a bucket of $\mathsf{\Theta}(n/k)$ items, with order maintained between buckets, but not within buckets.

## 3. A Variant with Optimal $O(logk)$ Worst-Case Time per Operation

**Outline and features.**Let $N=12k$. For illustrating the main ideas, assume now that $n\ge N$. The buckets are linked in a doubly-linked linear list $\mathcal{B}$, in key order; adding two links between the last and the first bucket yields a circular list $\mathcal{C}$, referred to as the round robin list. We note that $\mathcal{B}$ and $\mathcal{C}$ are two views of the same data structure.

**Elements of the design.**We highlight: (i) Use of the priority queue $\mathcal{H}$ to keep the number of buckets under control; (ii) use of the round robin process to detect large buckets, and (iii) running the procedures involved at different rates as needed to ensure that certain task deadlines and precedence constraints among them are met. The data structure maintains the following two invariants:

- $\mathcal{I}1$
- Each bucket contains between 1 and $n/(3k)$ elements; there is no limit from below imposed on the bucket size.
- $\mathcal{I}2$
- The number of buckets is between $3k$ and $N=12k$, as implied by the maximum bucket size and a later argument based on the rules of operation (on merging adjacent buckets); see Action 2 and Lemma 1.

**Action 1.**Execute the requested operation: Either add a new element to the respective bucket, or delete an arbitrary element from it. If the operation bucket becomes empty as a result of the current Delete operation, it is deleted, and $\mathcal{B}$, $\mathcal{H}$ (and t) are correspondingly updated to reflect this change in $O(logk)$ time. Status updates in the current two buckets are made, if needed. If a median finding procedure or a follow up procedure is under way in the current operation bucket or the current round robin bucket (see details below), the next segment consisting of 500 (or less) elementary operations of this background procedure is executed. These are instructions usually counted in standard analyses of algorithms, such as arithmetic operations, data movements, comparisons, etc. Specifically, we assume that the median of n elements can be found in at most $10n$ elementary operations.

**Action 2 (merge-test).**Let $\sigma :=s(\mathtt{b})+s({\mathtt{b}}^{+})$ be the minimum value at the top of the heap $\mathcal{H}$. If $\sigma \le 5n/(30k)$, merge the two buckets into one: $\mathtt{b}\cup {\mathtt{b}}^{+}\to \mathtt{b}$, and update the tree $\mathcal{A}$, the bucket list $\mathcal{B}$ and the binary heap $\mathcal{H}$ to reflect this change: (i) Delete the two buckets that are merged and insert the new one that results into $\mathcal{A}$ and $\mathcal{B}$; this only involves simple list handling and adjusting attributes at the $O(logk)$ nodes of $\mathcal{A}$ on the $O(1)$ search paths involved. (ii) extract the minimum element from $\mathcal{H}$ and insert the two new sum of sizes of two adjacent buckets formed by the new bucket into $\mathcal{H}$ (if they exist).

**Action 3 (finalizing a split).**Similar to the merge operations in Action 2, finalizing the split can be completed in $O(logk)$ time: It essentially involves updating $\mathcal{A}$, $\mathcal{B}$, and $\mathcal{H}$. It will be shown subsequently that the size of any new bucket resulting from a split is in the range $[4n/(30k),6n/(30k)]$.

**Splitting a large bucket.**For simplicity of exposition and without loss of generality, we may assume that $n\ge ck$, for a suitable constant $c>0$ (one can take $c=130$). It is worth noting that a bucket may become large by repeated deletions from other buckets leading to a reduction in the total number of items, n; moreover, by the same reasoning, several buckets may become large at the same time.

**Remark**

**1.**

**Analysis of merging buckets and maintaining the two invariants.**To prove that the two invariants $\mathcal{I}1$ and $\mathcal{I}2$ are maintained, we need the following key fact.

**Lemma**

**1.**

**Proof.**

**Summary of the analysis.**As seen from the preceding paragraphs and the fact that the number of buckets is $t=O(k)$, the total time per operation is $O(logt)+O(logk)+O(1)=O(logk)$, as required.

## 4. Conclusions

#### 4.1. Technical Remarks

`Insert`,

`Delete`and

`Findmin`operations. In contrast, the $O(log1/\epsilon )$ worst-case complexity per operation of the selectable sloppy heap is optimal (where $\epsilon \sim 1/k$).

#### 4.2. Applications and Concluding Remarks

## Funding

## Conflicts of Interest

## Appendix A

**Lower bound.**Suppose the delete operation always removes one of the L smallest items. Then to sort n items: (a) Insert them, (b) do repeated deletion, and (c) sort the sequence of deleted items in the order created by the successive deletions by executing only $n\lceil logL\rceil $ comparisons.

## References

- Blum, M.; Floyd, R.W.; Pratt, V.; Rivest, R.L.; Tarjan, R.E. Time bounds for selection. J. Comput. Syst. Sci.
**1973**, 7, 448–461. [Google Scholar] [CrossRef][Green Version] - Floyd, R.W.; Rivest, R.L. Expected time bounds for selection. Commun. ACM
**1975**, 18, 165–172. [Google Scholar] [CrossRef] - Hyafil, L. Bounds for selection. SIAM J. Comput.
**1976**, 5, 109–114. [Google Scholar] [CrossRef] - Schönhage, A.; Paterson, M.; Pippenger, N. Finding the median. J. Comput. Syst. Sci.
**1976**, 13, 184–199. [Google Scholar] [CrossRef][Green Version] - Yap, C.K. New upper bounds for selection. Commun. ACM
**1976**, 19, 501–508. [Google Scholar] [CrossRef] - Cormen, T.H.; Leiserson, C.E.; Rivest, R.L.; Stein, C. Introduction to Algorithms, 3rd ed.; MIT Press: Cambridge, MA, USA, 2009. [Google Scholar]
- Kleinberg, J.; Tardos, É. Algorithm Design; Pearson & Addison–Wesley: Boston, MA, USA, 2006. [Google Scholar]
- Mitzenmacher, M.; Upfal, E. Probability and Computing: Randomized Algorithms and Probabilistic Analysis; Cambridge University Press: Cambridge, UK, 2005. [Google Scholar]
- Chen, K.; Dumitrescu, A. Select with groups of 3 or 4. In Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS 2015), Victoria, BC, Canada, 5–7 August 2015; Volume 9214, pp. 189–199. [Google Scholar]
- Ajtai, M.; Komlós, J.; Steiger, W.L.; Szemerédi, E. Optimal parallel selection has complexity O(log logn). J. Comput. Syst. Sci.
**1989**, 38, 125–133. [Google Scholar] [CrossRef] - Battiato, S.; Cantone, D.; Catalano, D.; Cincotti, G.; Hofri, M. An efficient algorithm for the approximate median selection problem. In Proceedings of the 4th Italian Conference on Algorithms and Complexity (CIAC 2000), Rome, Italy, 1–3 March 2000; Volume 1767 of LNCS, pp. 226–238. [Google Scholar]
- Bent, S.W.; John, J.W. Finding the median requires 2n comparisons. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC 1985), Providence, RI, USA, 6–8 May 1985; pp. 213–216. [Google Scholar]
- Cunto, W.; Munro, J.I. Average case selection. J. ACM
**1989**, 36, 270–279. [Google Scholar] [CrossRef] - Dor, D.; Håstad, J.; Ulfberg, S.; Zwick, U. On lower bounds for selecting the median. SIAM J. Discret. Math.
**2001**, 14, 299–311. [Google Scholar] [CrossRef] - Dor, D.; Zwick, U. Finding the αnth largest element. Combinatorica
**1996**, 16, 41–58. [Google Scholar] [CrossRef] - Dor, D.; Zwick, U. Selecting the median. SIAM J. Comput.
**1999**, 28, 1722–1758. [Google Scholar] [CrossRef] - Fussenegger, F.; Gabow, H.N. A counting approach to lower bounds for selection problems. J. ACM
**1979**, 26, 227–238. [Google Scholar] [CrossRef] - Gasarch, W.; Kelly, W.; Pugh, W. Finding the ith largest of n for small i,n. SIGACT News
**1996**, 27, 88–96. [Google Scholar] [CrossRef] - Hadian, A.; Sobel, M. Selecting the t-th largest using binary errorless comparisons. Comb. Theory Its Appl.
**1969**, 4, 585–599. [Google Scholar] - Hoare, C.A.R. Algorithm 63 (PARTITION) and algorithm 65 (FIND). Commun. ACM
**1961**, 4, 321–322. [Google Scholar] [CrossRef] - John, J.W. A new lower bound for the set-partitioning problem. SIAM J. Comput.
**1988**, 17, 640–647. [Google Scholar] [CrossRef] - Kirkpatrick, D.G. A unified lower bound for selection and set partitioning problems. J. ACM
**1981**, 28, 150–165. [Google Scholar] [CrossRef] - Paterson, M. Progress in selection. In Proceedings of the 5th Scandinavian Workshop on Algorithm Theory (SWAT 1996), Reykjavík, Iceland, 3–5 July 1996; Volume 1097, pp. 368–379. [Google Scholar]
- Yao, A.; Yao, F. On the average-case complexity of selecting the kth best. SIAM J. Comput.
**1982**, 11, 428–447. [Google Scholar] [CrossRef] - Yao, F. On Lower Bounds for Selection Problems, Technical Report MAC TR-121; Massachusetts Institute of Technology: Cambridge, MA, USA, 1974. [Google Scholar]
- Knuth, D.E. The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed.; Addison–Wesley: Reading, MA, USA, 1998. [Google Scholar]
- Hofri, M. Optimal selection and sorting via dynamic programming. ACM J. Exp. Algorithmics
**2013**, 18, 2–3. [Google Scholar] [CrossRef] - Baase, S. Computer Algorithms: Introduction to Design and Analysis, 2nd ed.; Addison-Wesley: Reading, MA, USA, 1988. [Google Scholar]
- Dasgupta, S.; Papadimitriou, C.; Vazirani, U. Algorithms; Mc Graw Hill: New York, NY, USA, 2008. [Google Scholar]
- Aho, A.V.; Hopcroft, J.E.; Ullman, J.D. Data Structures and Algorithms; Addison–Wesley: Reading, MA, USA, 1983. [Google Scholar]
- Jayapaul, V.; Munro, J.I.; Raman, V.; Satti, S.R. Sorting and selection with equality comparisons. In Proceedings of the 14th International Symposium on Algorithms and Data Structures, Victoria, BC, Canada, 5–7 August 2015; Volume 9214, pp. 434–445. [Google Scholar]
- Kirkpatrick, D.G. Closing a long-standing complexity gap for selection: V
_{3}(42) = 50. In Space-Efficient Data Structures, Streams, and Algorithms—Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday; Brodnik, A., López-Ortiz, A., Raman, V., Viola, A., Eds.; Springer: Berlin/Heidelberg, Germany, 2013; Volume 8066, pp. 61–76. [Google Scholar] - Alexandrescu, A. Fast deterministic selection. In Proceedings of the 16th International Symposium on Experimental Algorithms (SEA 2017), London, UK, 21–23 June 2017; pp. 24:1–24:19. [Google Scholar]
- Chan, T.M. Quake heaps: A simple alternative to Fibonacci heaps. In Space-Efficient Data Structures, Streams, and Algorithms—Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday; Brodnik, A., López-Ortiz, A., Raman, V., Viola, A., Eds.; Springer: Berlin/Heidelberg, Germany, 2013; Volume 8066, pp. 27–32. [Google Scholar]
- Chazelle, B. The soft heap: An approximate priority queue with optimal error rate. J. ACM
**2000**, 47, 1012–1027. [Google Scholar] [CrossRef] - Fredman, M.; Rutgers University, New Brunswick, NJ, USA. Personal communication, 2016.
- Cole, R. Slowing down sorting networks to obtain faster sorting algorithms. J. ACM
**1987**, 34, 200–208. [Google Scholar] [CrossRef] - Fredman, M. Comments on Dumitrescu’s “A Selectable Sloppy Heap”. arXiv, 2016; arXiv:1610.02953. [Google Scholar]
- Estivill-Castro, V.; Wood, D. Sorting, measures of disorder, and worst-case performance. In New Results and New Trends in Computer Science; Maurer, H., Ed.; Springer: Berlin/Heidelberg, Germany, 1991; Volume 555, pp. 124–131. [Google Scholar]
- Manilla, H. Measures of presortedness and optimal sorting algorithms. IEEE Trans. Comput.
**1985**, 34, 318–325. [Google Scholar] [CrossRef] - Chazelle, B. A minimum spanning tree algorithm with inverse-Ackermann type complexity. J. ACM
**2000**, 47, 1028–1047. [Google Scholar] [CrossRef][Green Version] - Karger, D.R.; Klein, P.N.; Tarjan, R.E. A Randomized linear-time algorithm to find minimum spanning trees. J. ACM
**1995**, 42, 321–328. [Google Scholar] [CrossRef]

© 2019 by the author. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).