Master’s Thesis Presentation • Algorithms and Complexity — Selectable Heaps and Their Application to Lazy Search TreesExport this event to calendar

Wednesday, April 21, 2021 — 3:00 PM EDT

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.

Location 
Online presentation
200 University Avenue West

Waterloo, ON N2L 3G1
Canada
Event tags 

S M T W T F S
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  1. 2021 (166)
    1. November (1)
    2. October (3)
    3. September (19)
    4. August (20)
    5. July (17)
    6. June (11)
    7. May (16)
    8. April (27)
    9. March (20)
    10. February (13)
    11. January (19)
  2. 2020 (217)
    1. December (18)
    2. November (12)
    3. October (7)
    4. September (21)
    5. August (28)
    6. July (14)
    7. June (18)
    8. May (16)
    9. April (20)
    10. March (16)
    11. February (25)
    12. January (22)
  3. 2019 (255)
  4. 2018 (217)
  5. 2017 (36)
  6. 2016 (21)
  7. 2015 (36)
  8. 2014 (33)
  9. 2013 (23)
  10. 2012 (4)
  11. 2011 (1)
  12. 2010 (1)
  13. 2009 (1)
  14. 2008 (1)