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.
On
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.
On
Treaps are awesome variant of balanced binary search tree. There do exist many algorithms to balance binary trees, but most of them are horrible things with tons of special cases to handle. On the other hand , it is very easy to code Treaps.By making some use of randomness, we have a BBT that is expected to be of logarithmic height. Some good problems to solve using treaps are -- http://www.spoj.com/problems/QMAX3VN/ ( Easy level ) http://www.spoj.com/problems/GSS6/ ( Moderate level )
On
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:
On
Let's say you have a company and you want to create an inventory tool:
Be able to (efficiently) search products by name so you can update the stock.
Get, at any time, the product with the lowest items in stock, so that you are able to plan your next order.
One way to handle these requirements could be by using two different data structures: one for efficient search by name, for instance, a hash table, and a priority queue to get the item that most urgently needs to be resupplied. You have to manage to coordinate those two data structures and you will need more than twice memory. if we sort the list of entries according to name, we need to scan the whole list to find a given value for the other criterion, in this case, the quantity in stock. Also, if we use a min-heap with the scarcer products at its top, then we will need linear time to scan the whole heap looking for a product to update.
Treap is the blend of tree and heap. The idea is to enforce BST’s constraints on the names, and heap’s constraints on the quantities.
Product names are treated as the keys of a binary search tree.
The inventory quantities, instead, are treated as priorities of a heap, so they define a partial ordering from top to bottom. For priorities, like all heaps, we have a partial ordering, meaning that only nodes on the same path from the root to leaves are ordered with respect to their priority. In the above image, you can see that children nodes always have a higher stock count than their parents, but there is no ordering between siblings.
On
Any subtree in Treap is also a Treap (i.e. satisfies BST rule as well as min- or max- heap rule too). Due to this property, an ordered list can be easily split, or multiple ordered lists can be easily merged using Treaps than using an RB Tree. The implementation is easier. Design is also easier.
I can not provide you any real-world examples. But I do use treaps to solve some problems in programming contests:
These are not actually real problems, but they make sense.