
 { treaps
Tue Sep  7 12:46:27 PDT 2004
 }

  function treapFind(root:treap; var key:idType):treap;
   begin
    if root = nil then treapFind := nil
    else if root^.item = key then treapFind := root
    else if key < root^.item then treapFind := treapFind(root^.left,key)
    else treapFind := treapFind(root^.right,key);
   end;

  procedure treapRotateLeft(var root:treap);
    {input conditions: root <> nil, root^.right <> nil}
   var
    r,s:treap;
   begin
    if root = nil then writeln('Cannot left rotate')
    else if root^.right = nil then writeln('Cannot left rotate')
    else
     begin
      r := root;
      s := root^.right;
      r^.right := s^.left;
      s^.left := r; 
      root := s;
     end
   end;

  procedure treapRotateRight(var root:treap);
    {input conditions: root <> nil, root^.left <> nil}
   var
    r,s:treap;
   begin
    if root = nil then writeln('Cannot right rotate')
    else if root^.left = nil then writeln('Cannot right rotate')
    else
     begin
      r := root;
      s := root^.left;
      r^.left := s^.right;
      s^.right := r; 
      root := s;
     end
   end;

  procedure treapWrite(root:treap;level:integer);
   var
    i:integer;
   begin
    if root <> nil then
     begin
      treapWrite(root^.right,level+1);
      write('':level);writeln(root^.item,'':27-level,root^.priority:17:14);
      treapWrite(root^.left,level+1);
     end;
   end;

  function treapCount(root:treap):integer;
   begin
    if root = nil then treapCount := 0
    else treapCount := 1 + treapCount(root^.left)+treapCount(root^.right);
   end;

  function treapTotalPathLength(root:treap; level:integer):integer;
   begin
    if root = nil then treapTotalPathLength := 0
    else treapTotalPathLength := level
                         + treapTotalPathLength(root^.left,level+1)  
                         + treapTotalPathLength(root^.right,level+1);
   end;

  function treapAveragePathLength(root:treap):double;
   begin
    if root = nil then
     treapAveragePathLength := 0
    else
     treapAveragePathLength := treapTotalPathLength(root,0)/treapCount(root);
   end;

  procedure treapDelete(var root:treap; x:idType);
   begin
{writeln('Deleting ',x);}
    if root <> nil then
     if root^.item = x then
      if root^.right = nil then
{begin}
{writeln('root^.right = nil');}
       root := root^.left
{;end}
      else if root^.left = nil then
{begin}
{writeln('root^.left = nil');}
       root := root^.right
{;end}
      else
       begin
{writeln('Start treapRotateLeft');}
        treapRotateLeft(root);
{writeln('Finish treapRotateLeft');}
        treapDelete(root^.left,x);
       end
    else if x < root^.item then treapDelete(root^.left,x)
    else treapDelete(root^.right,x);
{writeln('Deleted ',x);}
   end;
       
  procedure treapInsert(var root:treap; key:idType);
   begin
    if root = nil then
     begin
      new(root);
      root^.item := key;
      root^.priority := random;
      root^.left := nil;
      root^.right := nil;
     end
    else if root^.item = key then writeln('Duplicate item not inserted.')
    else if key < root^.item then
     begin
      treapInsert(root^.left,key);
      if root^.priority > root^.left^.priority then treapRotateRight(root);
     end
    else
     begin
      treapInsert(root^.right,key);
      if root^.priority > root^.right^.priority then treapRotateLeft(root);
     end
   end;

  procedure itemLoadTreap(var root:treap);
   var
    x:idType;
   begin
    root := nil;
    while not eof do
     begin
      readln(x);
      treapInsert(root, x);
     end;
   end;

