STRUCTURE tip:Tree
          node(left:Tree,key:number,right:Tree):Tree.

%***************************************************************************
%********************** Function Pop, pg.151  ***************************

FUNCTION Pop(h:tree):tree;
BEGIN
  If (h = tip) Then tip;
  If ( (h != tip) And (left(h) = tip)  ) Then tip;
  If ( (h != tip) And (left(h) != tip) And (Less(Depth(right(h)),Depth(left(h))) = True) )
                  Then node(Pop(left(h)),key(h),right(h));

END.


%***************************************************************************
%********************** Function Pop, pg.152  ***************************

FUNCTION Swap(h:tree):Boolean;
BEGIN

  IF h = tip then tip;
  If ( (h != tip) And (left(h) = tip) ) Then tip;

  If ( (h != tip) And (left(h) != tip) And (Less(Depth(right(h)),Depth(left(h))) = True) )  
                  Then node(Pop(left(h)),Bottom(h),right(h));

  If ( (h != tip) And (left(h) != tip) And (Less(Depth(right(h)),Depth(left(h))) = False))  
                  Then node(left(h),Bottom(h),Pop(right(h)));

END.

%***************************************************************************
%********************** Function Sift, pg.152  *****************************

%FUNCTION Sift(h:tree):tree;
%BEGIN
%  If h = tip then tip;
%
%  If ( (h != tip) And (left(h) = tip) ) Then h;
%
%If ((h != tip) And (left(h) != tip) And (Equal(key(h),MinKey(h,left(h),right(h))) = True))
%                 Then h;
%
%  If ((h != tip) And (left(h) != tip) And 
%                     (Equal(key(left(h)),MinKey(h,left(h),right(h))) = True))
%                 Then node(Sift(node(left(left(h)),key(h),right(left(h)))),
%                           key(left(h)),right(h));
%
%  If ((h != tip) And (left(h) != tip) And 
%                     (Equal(key(right(h)),MinKey(h,left(h),right(h))) = True))
%                 Then node(left(h),key(right(h)),
%                           Sift(node(left(right(h))),key(h),right(right(h))));
%
%END.


%*******************************************************************************
%********************** Function HeapSort, pg.153  *****************************
                   
%FUNCTION HeapSort(h:Tree):list;
%BEGIN
%If h = tip then empty;
%If h != tip then add(key(h),HeapSort(Sift(Swap(h))));
%END.
