For an array A = [a1, a2, a3, a4] of distinct numbers, there are two main ways to build a heap, as described in class. In parts (a) and (b) of this problem you must show what comparisons each method will make, in the form of a binary decision tree, following these formatting rules: Each leaf should contain output in the form of some permutation of the input subscripts in A (e.g., you should write 3124 it you conclude that the constructed heap is A = [a3, a1, a2, a4]. Within each node, write only the subscripts, with the smaller one on the left (e.g., comparing a3 to a1 should be written as 1:3) When youre comparing values x and y, branch left when

(a) Do the above (draw the decision tree) for the forward method.

(b) Do the above (draw the decision tree) for the reverse method.

(c) Describe your own heap-building algorithm that specifically handles inputs of size 4, and draw the corresponding decision tree that uses fewer decisions in the worst-case compared to the methods in (a) and (b). Your algorithm should be described in English, not pseudocode.