Hacker News Reader

I was thinking of treaps;

https://en.m.wikipedia.org/wiki/Treap

Some, but not all, treaps have a node weight that is updated in a probabilistic fashion. The act of balancing the tree is still deterministic, but the weights of each node are randomized.

I keep trying to find a use for treaps, but haven't had a project that needed it. In particular, the value of a balanced tree is in consistent cost of lookups for arbitrary elements. But if you are mixing entries that are accessed often with those that are not, having an 8:1 access time ratio between the two would be a feature not a bug.

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

Reply on news.ycombinator.com