Dynamic Optimality Refuted – For Tournament Heaps
The dynamic optimality conjecture is the unproven hypothesis that splay trees can serve any sequence of operations with at most a constant times the cost of the best binary-search-tree (BST) based method, even if we allow the latter to know the sequence of accesses in advance (i.e., to work in “offline” mode). Despite decades of active research and a collection of related deep results the main conjecture remains open, and so is the question whether there exists any dynamically optimal BST algorithm.
In this paper, we show that the corresponding question for tournament heaps can be answered with a very definitive “No”.
In the tournament-tree model, keys are stored in the leaves of a binary tree, with internal nodes serving as “routers” only. Each internal node maintains a copy of the smallest key in its subtree, allowing efficient implementations of the standard priority-queue operations insert, extract-min and decrease-key.
Since (tournament) heaps allow many more configurations than BSTs – the keys do not have to be sorted – the choice of the tree restructuring primitive becomes important. We consider a pointer-machine model that allows to keep a given number, $k$, of fingers into the tree, used for restructuring the tree. Varying $k$ allows to study in a uniform fashion how the power of the restructuring operation affects the complexity of serving a sequence of requests.
We prove a strong separation between offline and online algorithms in this model, for any number of fingers. In particular, a competitive ratio of $o(\sqrt{\log n})$ is unattainable for any tournmanent-tree model.