Comment by vnorilo

I used a persistent treap for a lock free priority queue (swap in a new root at insertion). It felt nice but to be honest, didn't do a comprehensive comparison to alternate implementation strategies.

edit: looks like at least one other has has the same idea https://github.com/lthibault/treap