Applications of beyond-worst-case heaps

Can we construct heaps with interesting beyond-worst-case properties? And how can we use them for algorithm design? We will discuss a particular heap property – the working set property – and its applications for Dijkstra’s algorithm and the problem of sorting numbers under partial information.

Joint work with Bernhard Haeupler, Richard Hladík, John Iacono, Robert Tarjan, Jakub Tětek