Let T be the following table:
\(\begin{array}{|c|c|c|c|c|c|c|c|c|c|}\hline
3 & 5& 1 & 6 & 8 &11 &2 &4 & 9 & 10\\\hline
\end{array}\)

• Build the Max-Heap. You should represent the heap obtained after the insertion of each element of T.
• Add the value 13 to the above heap. Represent graphically all the iterations.
• Represent the heap above obtained in the form of a table.
• Give the worst time complexity of searching the maximum value?
• Give the worst time complexity of searching the minimum value?
  
  

Building the Max-Heap
* Insert 3
	  3
* Insert 5
	  3
      5
 Percolate-up 5
	  5
      3
* Insert 1
	  5
      3       1
* Insert 6
	  5
      3       1
   6
 Percolate-up 6
	  5
      6       1
   3
 Percolate-up 6
	  6
      5       1
   3
* Insert 8
	  6
      5       1
   3     8
 Percolate-up 8
	  6
      8       1
   3     5
 Percolate-up 8
	  8
      6       1
   3     5
* Insert 11
	  8
      6       1
   3     5 11
 Percolate-up 11
	  8
      6       11
   3     5  1
 Percolate-up 11
	  11
      6       8
   3     5  1
* Insert 2
	  11
      6       8
   3     5  1   2
* Insert 4
	  11
      6       8
   3     5  1   2
 4
 Percolate-up 4
	  11
      6       8
   4     5  1   2
 3
* Insert 9
	  11
      6       8
   4     5  1   2
 3   9
 Percolate-up 9
	  11
      6       8
   9     5  1   2
 3   4
 Percolate-up 9
	  11
      9       8
   6     5  1   2
 3   4
* Insert 10
	  11
      9       8
   6     5  1   2
 3   4 10
 Percolate-up 10
	  11
      9       8
   6     10  1   2
 3   4 5
 Percolate-up 10
	  11
     10       8
   6     9  1   2
 3   4 5



Add 13
	       11
         10               8
    6         9       1       2
 3     4   5     13
 Percolate-up 13
	       11
         10               8
    6         13       1       2
 3     4   5     9
 Percolate-up 13
	       11
         13               8
    6         10       1       2
 3     4   5     9
 Percolate-up 13
	       13
         11               8
    6         10       1       2
 3     4   5     9

Representation as an array
|13|11|8|6|10|1|2|3|4|5|9|

Worst time complexity of searching the maximum value
O(1) since the maximum is at index 0

Worst time complexity of searching the minimum value
O(N/2) since the minimum is one of the leaves.
Number of leaves in a heap is equal to N/2 where N is total number of its elements.