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.

Acierate

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.

Arroba

If the hash value is used as priority, the priority may not be random or uniformly distributed. This may destroys the theory underlying treap – Diphosgene

@jason - A randomizing hash function should be used. See Aragon and Seidel: Randomized Search Trees section 7.1. – Arroba

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.

Bibber

You don't need treaps for the first one though. Can be solved by precomputing a persistent segment tree, and then in O(logN) per query. :) Popular SPOJ problem: spoj.com/problems/MKTHNUM – Malo

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.

Predestinarian

Answer 4

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 )

Imposition

Answer 5

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

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.

Reference

Tran

Answer 6

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.

Heroworship

If you have a new question, please ask it by clicking the Ask Question button. Include a link to this question if it helps provide context. - From Review – Goatish