# A Selectable Sloppy Heap
## 1 Introduction
** 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, [PERSON]'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 [PERSON] [26]. Computational results on the exact comparison complexity of finding the \(i\)th 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]. The selection problem is also of interest in an online or dynamic setting, where elements are inserted or deleted. A balanced binary search tree on \(n\) distinct elements can be augmented with a _size_ attribute for each node, thereby allowing the retrieval of an element of a given rank in \(O(\log n)\) time ([6], Ch. 14). We say that the \(i\)th smallest element has _rank_\(i\), where \(i=1,\ldots,n\), with ties broken arbitrarily. Further, determining the rank of an element in the data structure can also be done in \(O(\log n)\) time. Consequently, a dynamic order statistic operation (inserting a new element or deleting an element of a given rank) can be accomplished within the same time bound. Priority queues (_heaps_ in particular) are ubiquitous data structures; a typical operation set might include 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. A variant of a priority queue that allows dynamic maintenance of percentiles is the _soft heap_ data structure due to [PERSON] [35]; in addition to Create and Meld, the data structure accommodates Insert, Delete and Findmin (Delete \(x\) removes item \(x\)). Consider a sequence of \(m\geq n\) operations after its creation, that includes \(n\) Insert operations. For any \(0<\epsilon\leq 1/2\), a soft heap with error rate \(\epsilon\) supports each operation in constant amortized time, except for Insert which takes \(O(\log 1/\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 datastructure uses \(O(\log 1/\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: Let \(k\) be a fixed positive integer. A \"selectable sloppy heap\" (abbreviated \(\mathrm{ssh}\)) is a data structure for performing the following operations on a set \(S\) with \(n\) elements:  
1. [label=()]
2. Insert _x: a new element_ \(x\) _is inserted._
3. Delete _i: this deletes (and returns) some unspecified element_ \(x\) _which belongs to the_ \(i\)_th quantile group of the current set, where_ \(1\leq i\leq 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(k\log k)\) amortized time per operation for the first variant in Section 2; (ii) \(O(k\log k)\) worst-case time per operation for the second variant in Section 2; (iii) \(O(\log k)\) 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(\log k)\) worst-case time per operation.