Data Structures, Algorithms, & Applications in Java
Chapter 13, Exercise 21

The code for MinHblt can be obtained from that for MaxHblt by making a single change in the private method meld. The new method is given below. The changed line is shown in red. Of course, we must also change the names of the methods removeMax and getMax to removeMin and getMin.

The code for the complete class MinHblt, a sample test program, and output are given in the files MinHblt.* 
static HbltNode meld(HbltNode x, HbltNode y)
{
   if (y == null)
      return x;   // y is empty
   if (x == null)
      return y;   // x is empty

   // neither is empty, swap x and y if necessary
   if (x.element.compareTo(y.element) > 0)
   {// swap x and y
      HbltNode t = x;
      x = y;
      y = t;
   }
   // now x.element <= y.element

   x.rightChild = meld(x.rightChild, y);

   // swap subtrees of x if necessary and set x.s
   if (x.leftChild == null)
   {// left subtree is empty, swap the subtrees
       x.leftChild = x.rightChild;
       x.rightChild = null;
       x.s = 1;
    }
   else
   {  // swap only if left subtree has smaller s value
      if (x.leftChild.s < x.rightChild.s)
      {// swap subtrees
          HbltNode t = x.leftChild;
          x.leftChild = x.rightChild;  
          x.rightChild = t;
      }
      // update s value
      x.s = x.rightChild.s + 1;
   }
   return x;
}