A treap whose priorities come from an insertion counter

A treap keeps keys in BST order and priorities in min-heap order (every node's priority is smaller than its children's), restoring heap order after an ordinary BST insertion by rotating the new node upward. Normally each priority is drawn uniformly at random. To make runs reproducible, an engineer instead assigns the i-th inserted key priority i. Keys 1, 2, ..., n are then inserted in increasing order. What is the resulting tree's height?

36 of 46 in Data Structures & Algorithms