# Rotations in a treap

I have a treap like the first image and I want to reach the second image to restore min heap order property. I can't understand which kinds of rotations have been done.

Image 1

Image 2

Initially, node F is violating the heap invariant. Its priority is too small, and it needs to be moved up the treap. The only operation needed is a single rotation. If you are not already familiar, please read this Wikipedia entry. Here are some illustrative diagrams:

I've drawn snapshots of the rotation process below. In each diagram, I've marked where the rotation is about to happen with stars (e.g. *E:14*). The direction of rotation should be obvious: the goal is to get F up the tree! Notice that as long as F is violating the heap invariant, we're rotating the parent of F.

       G:3
/   \
B:6   K:8
/   \     \
A:11   D:9   L:12
/   \
C:16  *E:14*
\
F:2

G:3
/   \
B:6   K:8
/   \     \
A:11  *D:9*  L:12
/   \
C:16  F:2
/
E:14

G:3
/   \
*B:6*  K:8
/   \     \
A:11   F:2   L:12
/
D:9
/   \
C:16  E:14

*G:3*
/   \
F:2    K:8
/        \
B:6         L:12
/   \
A:11   D:9
/   \
C:16  E:14

F:2
/   \
B:6    G:3
/   \     \
A:11   D:9   K:8
/   \    \
C:16  E:14  L:12


There are some really nice properties of rotations which make this work. Obviously rotations preserve the in-order traversal of the tree. But also notice that, whenever a subtree is detached/reattached during a rotation, there is never a priority inversion (i.e. you never attach a subtree as a child of a node with a larger priority).