Trees and heaps: the many faces of basic data structures

Prelegent(ci)

Laszlo Kozma

Afiliacja

TU Eindhoven

Termin

19 kwietnia 2018 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

Binary search trees (BSTs) and heaps are the canonical comparison-based implementations of the dictionary and the priority queue data types. They are among the most extensively studied structures in computer science, yet, many basic questions about them
remain open. What is the best strategy for updating a BST in response to queries? Is there a single strategy that is close to optimal for every possible scenario? Are Splay trees [Sleator and Tarjan, 1983] such an instance-optimal data structure? For which inputs can we improve upon the logarithmic cost per query?

Our current understanding of the heap model is similarly incomplete. Fibonacci heaps [Fredman and Tarjan, 1984] (and many of their proposed alternatives) are theoretically optimal in a worst-case, amortized sense, but perform operations outside the "pure"
comparison-based heap model -- in addition to being complicated in practice. Is there a simple, "self-adjusting" alternative to Fibonacci heaps? Is there, by analogy to BSTs, an "input-sensitive" heap, i.e. one that adapts to various usage patterns? Are the BST and the heap problems somehow related? In my talk I will present some old and new results related to this family of questions.

---