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 1Image 2
Rotations in a treap
trees;heaps;binary search trees
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:https://upload.wikimedia.org/wikipedia/commons/2/23/Tree_rotation.pnghttps://upload.wikimedia.org/wikipedia/commons/3/31/Tree_rotation_animation_250x250.gifI'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:12There 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).