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.