Selectable Heaps and Optimal Lazy Search Trees

We show the $O(\log n)$ time extract minimum function of efficient priority queues can be generalized to the extraction of the $k$ smallest elements in $O(k \log(n/k))$ time, where we define $\log(x)$ as $\max(\log_2(x), 1)$. We first show heap-ordered tree selection (Kaplan et al., SOSA '19) can be applied on the heap-ordered trees of the classic Fibonacci heap to support the extraction in $O(k \log(n/k))$ amortized time. We then show selection is possible in a priority queue with optimal worst-case guarantees by applying heap-ordered tree selection on Brodal queues (SODA '96), supporting the operation in $O(k \log(n/k))$ worst-case time. Via a reduction from the multiple selection problem, $\Omega(k \log(n/k))$ time is necessary if insertion is supported in $o(\log n)$ time. We then apply the result to lazy search trees (Sandlund & Wild, FOCS '20), creating a new interval data structure based on selectable heaps. This gives optimal $O(B+n)$ time lazy search tree performance, lowering insertion complexity into a gap $\Delta_i$ to $O(\log(n/|\Delta_i|))$ time. An $O(1)$ time merge operation is also made possible when used as a priority queue, among other situations. If Brodal queues are used, runtimes of the lazy search tree can be made worst-case in the general case of two-sided gaps. The presented data structure makes fundamental use of soft heaps (Chazelle, J. ACM '00), biased search trees, and efficient priority queues, approaching the theoretically-best data structure for ordered data.