Master’s Thesis Presentation • Algorithms and Complexity — Selectable Heaps and Their Application to Lazy Search Trees

Wednesday, April 21, 2021 3:00 pm - 3:00 pm EDT (GMT -04:00)

Please note: This master’s thesis presentation will be given online.

Lingyi Zhang, Master’s candidate
David R. Cheriton School of Computer Science

Supervisor: Professor J. Ian Munro

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. We  first show the heap-ordered tree selection of Kaplan et al. 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, 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.

We then apply the result to the lazy search trees of Sandlund & Wild, creating a new interval data structure based on selectable heaps. This gives optimal O(B +n) 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 under certain conditions. If Brodal queues are used, all runtimes of the lazy search tree can be made worst-case. The presented data structure uses soft heaps of Chazelle, biased search trees, and efficient priority queues in a non-trivial way, approaching the theoretically-best data structure for ordered data.

To join this master’s thesis presentation on Zoom, please go to