An advantage of treaps is that is that there is a natural way to add aggregates. That is, you can put data in a node that summarises the underlying tree. These

An advantage of treaps is that is that there is a natural way to add aggregates. That is, you can put data in a node that summarises the underlying tree. These are very useful in many applications and can be maintained in the same O(log n) bound that you get for insertion and deletion. I think it might be possible to get the same effect in skiplists, but it wouldn't be nearly as natural. On the other hand, skiplists are just sorted lists that can be maintained in O(log n) time, which is a conceptually very nice thing. The GSequence data structure in glib is such a sorted list, but implemented internally with a treap, so it's possible to get that type of API with treaps too.