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\mathrm{/}k))$ time (we define $\log (x)$ as $\max ({\log }_2(x),1)$.), which we prove optimal for comparison-based priority queues with $o(\log n)$ time insertion. We show heap-ordered tree selection (Kaplan et al., SOSA '19) can be applied on the heap-ordered trees of the classic Fibonacci heap and Brodal queue, in $O(k\log (n\mathrm{/}k))$ amortized and worst-case time, respectively. We additionally show the deletion of $k$ elements or selection without extraction can be performed on both heaps, also in $O(k\log (n\mathrm{/}k))$ time. Surprisingly, all operations are possible with no modifications to the original Fibonacci heap and Brodal queue data structures. 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 ${\mathrm{\Delta }}_i$ from $O(\log (n\mathrm{/}\mathrm{\mid }{\mathrm{\Delta }}_i\mathrm{\mid })+\log \log n)$ to $O(\log (n\mathrm{/}\mathrm{\mid }{\mathrm{\Delta }}_i\mathrm{\mid }))$ 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, all runtimes of the lazy search tree can be made worst-case.