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.
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
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).