COMP2011 Tutorial Solutions 6, Week 7

Trees, Heaps

R-6.14: Draw a (single) binary tree T such that
- each internal node of T stores a single character
- a preorder traversal of T yields EXAMFUN
- an inorder traversal of T yields MAFXUEN
The trick is to start by writing the words "MAFXUEN" underneath, then drawing the tree above it:
```
      E
     / \
    X   N
   / \
  A   U
 / \
M   F
```

Illustrate the performance of the heap-sort algorithm on the following input sequence: (2,5,6,8,9,4,10,3,11,7,1). Do it both with and without "bottom-up heap construction".

Insertion:

       2               2
     /   \           /   \
    5     6   =>    5     4
   / \   /         / \   /
  8   9 4         8   9 6

       2               2               2
     /   \           /   \           /   \
    5     4   =>    5     4   =>    3     4
   / \   / \       / \   / \       / \   / \
  8   9 6  10     3   9 6  10     5   9 6  10
 /               /               /
3               8               8
       2               2
     /   \           /   \
    3     4   =>    3     4
   / \   / \       / \   / \
  5   9 6  10     5   7 6  10
 / \ /           / \ /
8 11 7          8 11 9

       2               2               2               1
     /   \           /   \           /   \           /   \
    3     4   =>    3     4   =>    1     4   =>    2     4
   / \   / \       / \   / \       / \   / \       / \   / \
  5   7 6  10     5   1 6  10     5   3 6  10     5   3 6   10
 / \ / \         / \ / \         / \ / \         / \ / \
8 11 9 1        8 11 9 7        8 11 9 7        8 11 9 7

Removal:

       7               2               2
     /   \           /   \           /   \
    2     4   =>    7     4   =>    3     4
   / \   / \       / \   / \       / \   / \
  5   3 6  10     5   3 6  10     5   7 6  10
 / \ /           / \ /           / \ /
8 11 9          8 11 9          8 11 9
       9               3               3               3
     /   \           /   \           /   \           /   \
    3     4   =>    9     4   =>    5     4   =>    5     4
   / \   / \       / \   / \       / \   / \       / \   / \
  5   7 6  10     5   7 6  10     9   7 6  10     8   7 6  10
 / \             / \             / \             / \
8  11           8  11           8  11           9  11
      11               4                4
     /  \            /   \            /   \
    5    4   =>     5     11    =>   5     6
   / \  / \        / \   /  \       / \   / \
  8  7  6 10      8   7 6   10     8  7  11 10
 /               /                /
9               9                9
      9                5                5
    /   \            /   \            /   \
   5     6   =>     9     6     =>   7     6
  / \   / \        / \   / \        / \   / \
 8   7 11 10      8   7 11 10      8   9 11 10

      10               6
     /  \            /   \
    7    6   =>     7     10
   / \  /          / \   /
  8  9 11         8   9 11

      11               7               7
     /  \             / \             / \
    7   10   =>      11  10     =>   8   10
   / \              /  \            / \
  8   9            8    9          11  9

      9                8
     / \              / \
    8   10   =>      9  10 
   /                /
  11               11
      11               9
     /  \             / \
    9    10  =>     11   10 

     10
     /
    11

     11

Bottom-up insertion:

                                      -------------------  
       2               2               2               1
     /   \          -/---\-----------/---\-          /   \
    5     6         5     6   =>    1     4   =>    2     4
  -/-\---/-\-------/-\---/-\-      / \   / \       / \   / \
  8   9 4  10 =>  3   1 4  10     3   5 6  10     3   5 6  10
 / \ / \         / \ / \         / \ / \         / \ / \
3 11 7 1        8 11 7 9        8 11 7 9        8 11 7 9

Removal:

       9               2               2               2
     /   \           /   \           /   \           /   \
    2     4   =>    9     4   =>    3     4   =>    3     4
   / \   / \       / \   / \       / \   / \       / \   / \
  3   5 6  10     3   5 6  10     9   5 6  10     8   5 6  10
 / \ /           / \ /           / \ /           / \ /
8 11 7          8 11 7          8 11 7          9 11 7
       7               3               3
     /   \           /   \           /   \
    3     4   =>    7     4   =>    5     4
   / \   / \       / \   / \       / \   / \
  8   5 6  10     8   5 6  10     8   7 6  10
 / \             / \             / \
9  11           9  11           9  11
       11              4               4
      /  \           /   \           /   \
     5    4   =>    5    11  =>     5     6
    / \  / \       / \  /  \       / \   / \
   8  7  6 10     8  7  6  10     8   7 11 10
  /              /               /
 9              9               9
       9               5               5
     /   \           /   \           /   \
    5     6   =>    9     6  =>     7     6
   / \   / \       / \   / \       / \   / \
  8   7 11 10     8   7 11 10     8   9 11 10

       10              6
      /  \           /   \
     7    6   =>    7    10
    / \  /         / \   /
   8  9 11        8   9 11


       11              7              7
      /  \            / \            / \
     7   10   =>     11  10   =>    8  10
    / \             /  \           / \
   8   9           8    9         11  9

       9               8
      / \             / \
     8   10   =>     9  10
    /               /
   11              11

       11              9
      /  \            / \
     9   10   =>     11  10

       10
      /
     11

       11

C-7.17: Describe an algorithm that computes the kth smallest element of a set of n distinct integers in O(n + k log n) time.
Do bottom-up heap construction, which takes O(n) time.
Then call removeMinElement() k times, which takes O(k log n) time.

C-7.14: Let T be a heap storing n keys. Give an efficient algorithm for reporting all the keys in T that are smaller than or equal to a given query key x (which is not necessarily in T).

reportSmallerThan( Node node, Object x )
{
    if( node.isInternal() && node.element().isLessThanOrEqualTo( x ))
    {
        System.out.println( node.element );
        reportSmallerThan( node.leftChild(), x );
        reportSmallerThan( node.rightChild(), x );
    }
}

This method takes O(k) time.

Author: Alan Blair