[hinkley]

I have just started fiddling with treaps recently. Not applicable I suspect for a hardware cache but this thread has morphed a bit into conversations about software caches as well.

A treap is an unbalanced binary tree where the tree depth is proportional to the frequency of use to get fewer indirections per access (assuming an uneven distribution of lookups). Essentially it has a MFU or LFU queue built into it and now I'm curious about how it would behave as a cache data structure.