CpE 207 Data Structures Fall 2020/2021 Assignment #6 Q1 [15 pts] A kindergarten teacher wants to represent a list of her students' records (by their ID). For each child we would like to mark whether he is a boy or a girl. Suggest a data structure that supports the following operations in O(log n) time in the worst case, where n is the number of students (boys and girls) in the data structure when the operation is executed: Using algorithms: 1. Explain what data structure you would use, extra fields added to your data structure. 2. Explain how each of the above operations will be executed (write algorithms explaining their time complexity). a. Insert (SID,G) function - Insert a new students with student ID (SID) and gender (G) b. ChangeGender(k) - Change the student with SID = k to be a boy. c. Find Diff(k) function, Find the difference between the number of girls and the number of boys ( #of girls - #of boys 1) among all the students with SID smaller than k. Q2. [15 pts] Write and test a JAVA program that merges two heaps together the output should be a heap. Note: 1. Your function/algorithm should be well-structures and well-documented. 2. Indicate the expected time and space complexity of your function/algorithm