1
$\begingroup$

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 1

Image 2 Image 2

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.