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.
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.