If you’re on a phone, here’s an HTML version of the paper <a href="https://www.arxiv-vanity.com/papers/1806.06726/" rel="nofollow">https://www.arxiv-vanity.com/papers/1806.06726/</a>
A Cartesian tree (treap) with zip/merge change routine is a well known datastructure in competitive programming. The only difference from the paper would be rank selection algorithm - uniform instead of geometric.<p>Unclear if authors were aware of it.
Correct me if I'm wrong, but isn't this the "standard" [1] treap with split/merge (which is somewhat acknowledged in the footnote of page 8), simply with a different distribution of priorities? The result is certainly impressive, but it seems like a small modification to an otherwise known structure.<p>[1]: See here <a href="http://e-maxx.ru/algo/treap" rel="nofollow">http://e-maxx.ru/algo/treap</a> for an old reference of this structure. Google translate does a decent job with it, and the code is readable without translation.
> insertion and deletion can be done purely top-down, with O(1) expected restructuring time and exponentially infrequent occurrences of expensive restructuring. Certain kinds of deterministic balanced search trees, in particular weak AVL trees and red-black trees achieve these bounds in the amortized sense [3], but at the cost of somewhat complicated update algorithms.<p>It's a neat, novel data structure with O(1) typical insert and delete times. Very cool!
I'm curious about how expensive the restructuring is, and importantly, can that be "scheduled": can i violate some conditions and then do the expensive restructuring at a time that is convenient?
Data structure from competitive programming is also known as "treap with implicit keys", related question on stackoverflow: <a href="https://stackoverflow.com/questions/3497875/treap-with-implicit-keys" rel="nofollow">https://stackoverflow.com/questions/3497875/treap-with-impli...</a>
Any links to the implementation of this? The paper says that there's a concurrent implementation in the author's thesis, but Princeton charges $5 per copy of theses, so I can't view the actual implementation:<p><a href="https://dataspace.princeton.edu/jspui/handle/88435/dsp01gh93h214f" rel="nofollow">https://dataspace.princeton.edu/jspui/handle/88435/dsp01gh93...</a>
I wonder if this would be a good candidate for the basis of a persistent ("functional") data structure?<p>O(1) pointer changes for insert/remove is a good sign, since pointer changes tend to become <i>space</i> overhead in a persistent data structure.