Using Figure 8.1 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. 1:3 K1,2,3) 1:3 (2,1,3) (1,3,2) K3,1,2) (2,3,1) 3,2,1 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 (1), T(2), 2 (n)) indicates the ordering ar(1) S am (2) s... s an on). The shaded path indi cates the decisions made when sorting the input sequence (ai 6, az 8, a3 5); the permutation (3, 1,2) at the leaf indicates that the sorted ordering is a3 53 al 6 s a2 8. There are 3! 6 possible permutations of the input elements, so the decision tree must have at least 6 leaves