# A Selectable Sloppy Heap
## 2 Some Ideas and Preliminary Suboptimal Solutions
As such, the number of elements, \(n^{\prime}\), in the data structure at operation time (during \(\Phi^{\prime}\)), belongs to the interval  
\[\left[\left(1-\frac{1}{9k}\right)^{2}n,\left(1+\frac{1}{9k}\right)^{2}n\right]. \tag{2}\]  
The total number of operations in phases \(\Phi\) and \(\Phi^{\prime}\) is at most  
\[\frac{n}{9k}+\frac{n+n/(9k)}{9k}=\frac{2n}{9k}+\frac{n}{81k^{2}}=\left(1+\frac{ 1}{9k}\right)^{2}n-n. \tag{3}\]  
To verify that the data structure operates as intended, one needs to check that the rank of a deleted element belongs to the required interval (quantile group). The key observation is that any one operation can affect the rank of any element by at most 1: To be precise, only Insert or Delete of a smaller element can increase the rank of an element by 1 or decrease the rank of an element by 1, respectively. By the above observation, the rank of a deleted element lies in the interval  
\[\left[\frac{9i-5}{9k}n-\left(1+\frac{1}{9k}\right)^{2}n+n,\frac{9i-4}{9k}n+ \left(1+\frac{1}{9k}\right)^{2}n-n\right],\text{ where }1\leq i\leq k. \tag{4}\]  
We need to show that this rank belongs to the interval  
\[\left[\frac{i-1}{k}n^{\prime},\frac{i}{k}n^{\prime}\right]. \tag{5}\]It suffices to verify that  
\[\frac{9i-5}{9k}n-\left(1+\frac{1}{9k}\right)^{2}n+n\geq\frac{i-1}{k}\left(1+ \frac{1}{9k}\right)^{2}n, \tag{6}\]  
and respectively that  
\[\frac{9i-4}{9k}n+\left(1+\frac{1}{9k}\right)^{2}n-n\leq\frac{i}{k}\left(1- \frac{1}{9k}\right)^{2}n. \tag{7}\]  
Inequality (6) is equivalent to  
\[1+\frac{9i-5}{9k} \geq\left(1+\frac{1}{9k}\right)^{2}\left(1+\frac{i-1}{k}\right),\ \text{or}\] \[1+\frac{4}{9(k+i-1)} \geq 1+\frac{2}{9k}+\frac{1}{81k^{2}}.\]  
Since \(1\leq i\leq k\), it is enough to verify that  
\[O\left(\frac{n\log{k}}{n/(9k)}\right)=O\left(k\log{k}\right). \tag{1}\]0  
Inequality (7) is equivalent to  
\[O\left(\frac{n\log{k}}{n/(9k)}\right)=O\left(k\log{k}\right). \tag{1}\]1 \[O\left(\frac{n\log{k}}{n/(9k)}\right)=O\left(k\log{k}\right). \tag{1}\]2 \[O\left(\frac{n\log{k}}{n/(9k)}\right)=O\left(k\log{k}\right). \tag{1}\]3  
Similarly, this follows from the inequality \(1\leq i\leq k\). A third variant with \(O(\log k)\) amortized time per operationWe briefly describe an implementation achieving \(O(\log k)\) amortized time per operation that is tailored on the idea of a B-tree; this variant was suggested by [PERSON] (2006). Use a balanced binary search tree \(\mathcal{A}\) with \(\Theta(\log k)\) levels storing \(O(k)\) splitting keys at the leafs. Each leaf comprises a bucket of \(\Theta(n/k)\) items, with order maintained between buckets, but _not within_ buckets. As mentioned earlier, a balanced binary search tree on distinct elements can be augmented with a _size_ attribute for each node, thereby allowing the retrieval of an element of a given rank in time proportional to its height. Using this mechanism, \(\mathcal{A}\) can be augmented with such information allowing the retrieval of a leaf containing elements within a given quantile group, as needed for answering an operation request, in \(O(\log k)\) time. When an insertion causes a bucket to become too large, it gets split into two buckets by performing a median selection operation. The balanced binary search tree is correspondingly updated by deleting a leaf and inserting two new ones. Small buckets (due to deletions) get merged; the balanced binary search tree is correspondingly updated by deleting two leaves and inserting a new one. A bucket of size \(m\), once split, won't get split sooner than another \(\Omega(m)\) operations. When the number of elements doubles (or halves), a tree reorganization is triggered that partitions the present items into \(6k\) uniform sized buckets, so that the new common bucket size \(m\) is \(n/(6k)\) items. These event-triggered reorganizations ensure that buckets do not become too small unless they are target of deletions; similarly, buckets do not become too large unless they are target of insertions.