Dr. László Kozma, Eindhoven
“Trees and heaps: the many faces of basic data structures”

Abstract:

Binary search trees (BSTs) and heaps are the simplest 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 optimal for every possible scenario? Are Splay trees optimal? For which inputs can we improve upon the logarithmic cost per operation?

Our understanding of heaps is even more limited. Fibonacci heaps (and their relatives) are theoretically optimal in a worst-case, amortized sense, but they perform operations outside of a "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 two problems related?

In my talk I will present some old and new results pertaining to this family of questions.