When to use a treap

Question

Can anyone provide real examples of when is the best way to store your data is treap?

I want to understand in which situations treap will be better than heaps and tree structures.

If it's possible, please provide some examples from real situations.

I've tried to search cases of using treaps here and by googling, but did not find anything.

Thank you.

Answer 1

If hash values are used as priorities, treaps provide unique representation of the content.

Consider an order set of items implemented as an AVL-tree or rb-tree. Inserting items in different orders will typically end up in trees with different shapes (although all of them are balanced). For a given content a treap will always be of the same shape regardless of history.

I have seen two reasons for why unique representation could be useful:

1. Security reasons. A treap can not contain information on history.
2. Efficient sub tree sharing. The fastest algorithms for set operations I have seen use treaps.

Answer 2

I can not provide you any real-world examples. But I do use treaps to solve some problems in programming contests:

• http://poj.org/problem?id=2761
• http://poj.org/problem?id=3481

These are not actually real problems, but they make sense.

Answer 3

You can use it as a tree-based map implementation. Depending on the application, it could be faster. A couple of years ago I implemented a Treap and a Skip list myself (in Java) just for fun and did some basic benchmarking comparing them to TreeMap, and the Treap was the fastest. You can see the results here.

One of its greatest advantages is that it's very easy to implement, compared to Red-Black trees, for example. However, as far as I remember, it doesn't have a guaranteed cost in its operations (search is O(log n) with high probability), in comparison to Red-Black trees, which means that you wouldn't be able to use it in safety-critical applications where a specific time bound is a requirement.