Using Figure 8.1 of CLRS as a model, draw the decision tree for heapsort on 3 elements. Then find the number of comparisons between input elements needed for completing heapsort on 3 elements in the worst case.

1:2 2:3 1:3 1,2,3) 1:3 2:3 Figure 8.1 The decision tree for insertion sort operating on three elements. An internal node an- notated by i:j indicates a comparison between ai and aj. A leaf annotated by the permutation (T (I), (2), , (n)) indicates the ordering Ox(1) Ox(2)