Jess: Data Structures, Week 9

6.2 (b) Show the result of using the linear-time algorithm to build a binary heap using 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, and 2.

Initial heap:

          10
         /   \
        /     \
       /       \
      /         \
     12          1
    / \         / \
   /   \       /   \
  14    6     5     8
 / \   / \   / \   / \
15  3 9   7 4  11 13  2

After percolateDown(7):

          10
         /   \
        /     \
       /       \
      /         \
     12          1
    / \         / \
   /   \       /   \
  14    6     5     2
 / \   / \   / \   / \
15  3 9   7 4  11 13  8

After percolateDown(6):

          10
         /   \
        /     \
       /       \
      /         \
     12          1
    / \         / \
   /   \       /   \
  14    6     4     2
 / \   / \   / \   / \
15  3 9   7 5  11 13  8

After percolateDown(5):

          10
         /   \
        /     \
       /       \
      /         \
     12          1
    / \         / \
   /   \       /   \
  14    6     4     2
 / \   / \   / \   / \
15  3 9   7 5  11 13  8

After percolateDown(4):

          10
         /   \
        /     \
       /       \
      /         \
     12          1
    / \         / \
   /   \       /   \
  3     6     4     2
 / \   / \   / \   / \
15 14 9   7 5  11 13  8

After percolateDown(3):

          10
         /   \
        /     \
       /       \
      /         \
     12          1
    / \         / \
   /   \       /   \
  3     6     4     2
 / \   / \   / \   / \
15 14 9   7 5  11 13  8

After percolateDown(2):

          10
         /   \
        /     \
       /       \
      /         \
     3           1
    / \         / \
   /   \       /   \
  12    6     4     2
 / \   / \   / \   / \
15 14 9   7 5  11 13  8

After percolateDown(1):

           1
         /   \
        /     \
       /       \
      /         \
     3           2
    / \         / \
   /   \       /   \
  12    6     4     8
 / \   / \   / \   / \
15 14 9   7 5  11 13 10

6.3 Show the result of performing three deleteMin operations in the heap of the previous exercise.

After the first deleteMin:

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

After the second deleteMin:

           3
         /   \
        /     \
       /       \
      /         \
     6           4
    / \         / \
   /   \       /   \
  13    7     5     8
 / \   / \   / \   
15 14 12  9 10 11

After the third deleteMin (resulting heap):

           4
         /   \
        /     \
       /       \
      /         \
     6           5
    / \         / \
   /   \       /   \
  13    7     10    8
 / \   / \   /    
15 14 12  9 11