Treap Data Structure

Two things are given:

• The priority of your node ist independent of your data (it is a random number)
• The chance of the worst case you described is 2/(n!) (ascending/descending occurance of random numbers)

So the runtime can be considered (amortized) Log(n) (average runtime with the same (worst case) data).