Treap Insertion: Exercise
Consider the following (max-heap) treap, where the keys are the letters and the priorities are the integers:
![](/img/21/treap13.png)
Exercise Show the result of inserting the key M, including any necessary rotations. Assume the priority generated for the key M is 15.
Solution
We insert M following the insertion process of a regular BST (ignoring priorities):
![](/img/21/treap14.png)
We must now apply tree rotations to fix the max-heap order property. Since M is to the left of P, we apply a right rotation to bring M above P and P to the right of M:
![](/img/21/treap15.png)
Since the priority of M is larger than priority of T we must apply tree rotation again to bring M above T:
![](/img/21/treap16.png)
We must apply a rotation one last time; this time, however, we apply left rotation since M is to the right of J:
![](/img/21/treap17.png)
Notice the BST order property is maintained over the keys (letters) and the max-heap order property is maintained over the priorities (integers).