Data Structures, Algorithms, & Applications in C++
Chapter 12, Exercise 19

(a)

The first six calls to meld create the following six max leftist trees.

  5       7      20        9      15     30
 /       /      /         /      /      /
3       6      8         2      12     17

The next three calls to meld combine pairs of these trees to create the following three trees:

       7                20             30
     /   \            /   \           /   \
    6     5          8     9        17     15
         /                /                /
        3                2                12

Next, the first two trees are combined to get

                    20
                  /    \
                 9      8
               /   \
              7     2
            /  \
           6    5
               /
              3

Finally, we get:

                      30
                     /  \
                    20   17
                  /    \
                 9      15
               /   \    / \
              7     2  12  8
            /  \
           6    5
               /
              3

(b)

After inserting 10, we get:

                        30
                     /      \
                    20       17
                  /    \     /
                 9      15  10
               /   \    / \
              7     2  12  8
            /  \
           6    5
               /
              3

After inserting 18, we get:

                        30
                      /    \
                     /       \
                    /          \
                  20            18
                /    \          /
               9      15       17
             /   \    / \      /
            7    2  12   8    10
          /  \
         6    5
             /
            3

After inserting 11, we get:

                        30
                      /    \
                     /       \
                    /          \
                  20            18
                /    \          / \
               9      15       17  11
             /   \    / \      /
            7    2  12   8    10
          /  \
         6    5
             /
            3

After inserting 4, we get:

                        30
                      /    \
                     /       \
                    /          \
                  20            18
                /    \          / \
               9      15       17  11
             /   \    / \      /   /
            7    2  12   8    10   4
          /  \
         6    5
             /
            3

(c)

After removing the max element, we must meld the two subtrees:

                  20               18
                /    \             / \
               9      15          17  11
             /   \    / \         /   /
            7    2  12   8       10   4
          /  \
         6    5
             /
            3

The result is:

                  20      
                /    \    
              /        \
            /            \
           9              18 
         /   \            / \
        7    2          15   17
      /  \           /  \   /
     6    5         11  12  10
         /         /  \
        3         4    8

When the max element is removed, we must meld the two subtrees

           9              18 
         /   \            / \
        7    2          15   17
      /  \             /  \   /
     6    5           11  12  10
         /           /  \
        3           4    8

The result is:

                  18      
                /    \    
              /        \
            /            \
          15              17 
         /   \            / \
       11    12          9   10
      /  \             /  \
     4    8           7    2
                    /  \ 
                   6    5
                       /
                      3

When the max element is removed, we must meld the two trees:

          15              17 
         /   \            / \
       11    12          9   10
      /  \             /  \
     4    8           7    2
                    /  \
                   6    5
                       /
                      3

The result is:

                17 
              /    \
            /        \
          /            \
         9             15
       /  \           /  \
      7    2        11    12
    /  \           /  \   /
   6    5         4    8  10
       /
      3