Use trees to illustrate each heap a. Show the result of inserting 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, and 2, one at a time, into an initially empty binary heap. (show heap after each insert) b. Show the result of using the linear-time build heap operation using the same input.

Check the explanation

Explanation:

A)

  10      10       10         1              1

          /        /  \  -->  / \           /   \

        12       12    1    12   10       12     10

                                         /

                                       14

       1              1               1                1

     /   \           /  \           /    \           /    \

   12     10  -->   6    10       6       10  -->   6       5

  /  \            /  \          /   \    /        /  \     /

14    6         14    12      14    12  5        14   12 10

        1                 1                  1                 1

     /     \           /     \             /    \           /     \

    6       5         6       5          6       5   -->   3       5

  /  \     / \      /  \     / \       /   \    /  \      /  \    /  \

14    12 10   8   14    12 10   8    14    12 10    8    6   12 10    8

                 /                  /  \               /  \

               15                 15    3            15    14

After inserting all             1

                           /       \

                       3               2

                     /   \           /   \

                   6       7       5       4

                  / \     / \     / \     / \

                 15 14   12  9   10 11   13  8

b)

First level build :            10

                           /       \

                       12              1

                     /   \           /   \

                  14       6       5       8

                  / \     / \     / \     / \

                 15  3   9   7   4  11   13  2

       Heap bottom level:     10

                           /       \

                       12              1

                     /   \           /   \

                   3       6       4       2

                  / \     / \     / \     / \

                 15  14  9   7   5  11   13  8

       Heap next level up:     10

                           /       \

                       3               1

                     /   \           /   \

                   12      6       4       2

                  / \     / \     / \     / \

                 15  14  9   7   5  11   13  8

       Final heap:             1

                           /       \

                       3               2

                     /   \           /   \

                  12       6       4       8

                  / \     / \     / \     / \

                 15 14   9   7   5  11   13  10