English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We prove a separation between offline and online algorithms for finger-basedtournament heaps undergoing key modifications. These heaps are implemented bybinary trees with keys stored on leaves, and intermediate nodes tracking themin of their respective subtrees. They represent a natural starting point forstudying self-adjusting heaps due to the need to access the root-to-leaf pathupon modifications. We combine previous studies on the competitive ratios ofunordered binary search trees by [Fredman WADS2011] and on order-by-nextrequest by [Mart\'inez-Roura TCS2000] and [Munro ESA2000] to show that for anynumber of fingers, tournament heaps cannot handle a sequence of modify-keyoperations with competitive ratio in $o(\sqrt{\log{n}})$. Critical to thisanalysis is the characterization of the modifications that a heap can undergoupon an access. There are $\exp(\Theta(n \log{n}))$ valid heaps on $n$ keys,but only $\exp(\Theta(n))$ binary search trees. We parameterize themodification power through the well-studied concept of fingers: additionalpointers the data structure can manipulate arbitrarily. Here we demonstratethat fingers can be significantly more powerful than servers moving on a statictree by showing that access to $k$ fingers allow an offline algorithm to handleany access sequence with amortized cost $O(\log_{k}(n) + 2^{\lg^{*}n})$.

Dynamic Optimality Refuted -- For Tournament Heaps