Hacker News Reader

Comment by kilotaras | Hacker News Reader

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.

View on HN

  >> 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")

> ...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

Thanks for clarifying :)

Reply on news.ycombinator.com