6 ms·
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 ran
by kilotaras 8y ago
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.
Unclear if authors were aware of it.
- blacksmythe 8y ago>> One can view a zip tree as a treap (Seidel and Aragon 1996) in which priority ties are allowed and >> in which insertions and deletions are done by unmerging and merging paths ("unzipping" and "zipping")
- kilotaras 8y ago> ...rather than by doing rotations. DS i've mentioned is using unzip/zip (called split/merge), see [1] [1] https://cp-algorithms.com/data_structures/treap.html https://cp-algorithms.com/data_structures/treap.html
- blacksmythe 8y agoThanks for clarifying :)