When is a treap useful?

Question

In what kind of situation is a treap the optimal data structure to use? I have been searching for answers on this but haven't really found anything concrete.

There's another stackoverflow question asking when to use a treap but no real world examples are given there.

The most commonly given advantage seems to be that they are so much easier to implement than for example a red-black tree, but almost everyone uses pre-written implementations anyway, so it doesn't seem that relevant.

Theatrician

When I don't have a specific question but want to know when a data structure should be preferred, its generally related to time and space complexities for which I just see the wiki pages. They tell you the worst,average etc case complexities. en.wikipedia.org/wiki/Treap Just compare with wiki pages of others – Chittagong

Answer 1

It's an optimal data structure to use as an example in randomized algorithms classes.

OK, flippancy aside, the narrow advantages suggested by Aragon and Seidel include the following.

• They're simple. Yes, your standard library may have a red-black tree available, but it's likely that it doesn't provide enough hooks to do some of the interesting things that can be done with binary search trees (e.g., order statistics). Split and merge are much simpler too.

• They use slightly less space than red-black trees, assuming that the priorities are computed by hashing the keys. In practice this doesn't matter if the red-black trees can steal a pointer bit for color.

• They may be faster than red-black trees. I haven't searched for evidence either way.

The big downside is that the performance guarantees are in expectation only. People learned the hard way with hash tables that the oblivious adversary assumed by analyses of randomized algorithms usually isn't so oblivious in the real world.

I think it's fair to say that treaps were an interesting idea but one that turned out not to have a lot of practical impact. It's research. That happens.

Mollusc

Answer 2

One very unusual property of Treaps is that they are not sensitive to the order of the insertions/deletions.

Since insertion/deletion happens based on the random priority, if $n$ elements are added to an empty treap, irrespective of the order in which insertion happens, the treap will look exactly the same.

So an adversary cannot look at the treap and figure out the order in which the elements were inserted.

Campania

Answer 3

In a real-world example, treap is used in LFU Cache implementation. For LFU cache, hash map and treap are used.

Caching policies are named based on the eviction policy. In LFU cache, we purge least frequently used item. For this, each item holds the count variable that shows how many times they have been used.

But we have to be careful. We want to make sure that among the elements with the minimum number of entries, the oldest is removed first; otherwise, we could end up removing the latest entry over and over again, without giving it a chance to have its counter increased. So we have to keep track of two things: counter and time of insertion.

Jointure