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 https://zoom.us/j/92649210094?pwd=RTJHU1E2M1BYQUg3ZHFtN0syN3lkZz09.