Question

The height of a treap depends on the random priority. However, the probability distribution of the height of an treap is exactly the same as the probability distribution of the number of rounds in a quicksort algorithm, as long as we choose pivots in the quicksort uniformly at random. Please prove this.

Answer 1

Explanation:

Heap Property: The associated priority satisfy the heap property. The (max) heap property requires for every node that the priority at a node is greater than the priority of its two children.

THEOREM: For any set S of key-value pairs, there is exactly one treap T containing the key-value

pairs in S which satisfies the treap properties.

Proof: The key k with the highest priority in S must be the root node, since otherwise the tree would not be in heap order. Then, to satisfy the property that the treap is ordered with respect to the nodes’ keys, all keys in S less than k must be in the left subtree, and all keys greater than k must be in the right subtree. Inductively, the two subtrees of k must be constructed in the same manner.

Now, if you are given a set of elements with keys and priorities, how would you build a treap

out of them? Take the element with the largest priority, make that the root. Then partition around

that root based on keys to find the elements in the right and left subtrees and recurse. What does

this remind you of?

This procedure is exactly the procedure you do for quicksort. There is a straightforward relationship between the analysis of quicksort and the height of a treap