4 ms·
I was thinking of treaps; https://en.m.wikipedia.org/wiki/Treap https://en.m.wikipedia.org/wiki/Treap
by vnorilo 4y ago
I was thinking of treaps;
https://en.m.wikipedia.org/wiki/Treap https://en.m.wikipedia.org/wiki/Treap
- hinkley 4y agoSome, 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.
- vnorilo 4y agoI 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 https://github.com/lthibault/treap