2. "Optimal Sort": 1. (15 points) Construct the decision tree for heap sort on a heap with four elements (a1, a2, a3, a4). 2. (15 points) We learned that any comparison sort algorithm requires at least n log n comparisons in the worst case for inputs of size n. What can we say about the best case?