Name:________________________________________

1. (2 pts) Draw two different leftmost binary trees that represent a min-heap containing the keys 1, 2, 3, 4, 5, 6.
   
   
   
   
   
   
   
   
   
   
   
   
2. (1 pt) True or False: The tight worst-case running time for heapsort on n numbers is Theta(n).
   
   
   
   
   
   
3. (1 pt) True or False: The tight worst-case running time for the partition procedure (used in quicksort) on n numbers is Theta(n log n).
   
   
   
   
   
   
4. (1 pt) What pattern of splits gives the worst-case performance for quicksort?