Dynamic Optimality Refuted -- For Tournament Heaps

Understand

We prove a separation between offline and online algorithms for finger-based tournament heaps undergoing key modifications.

• These heaps are implemented by binary trees with keys stored on leaves, and intermediate nodes tracking the min of their respective subtrees.
• They represent a natural starting point for studying self-adjusting heaps due to the need to access the root-to-leaf path upon modifications.
• We combine previous studies on the competitive ratios of unordered binary search trees by [Fredman WADS2011] and on order-by-next request by [Mart\'inez-Roura TCS2000] and [Munro ESA2000] to show that for any number of fingers, tournament heaps cannot handle a sequence of modify-key operations with competitive ratio in $o(\sqrt{\log{n}})$.