(ai) (b) (c) (d) (e) Let 27, 21, 9, 43, 37, 83, 123, 33 and 97...

 

Transcribed Image Text:

(ai) (b) (c) (d) (e) Let 27, 21, 9, 43, 37, 83, 123, 33 and 97 be the elements of an array A which represents a binary tree T such that for node A[i] in T, the leftson and rightson are A[21] and A[2i + 1] respectively. Draw the binary tree which the array A represents. [2 marks] Convert the tree into a maxheap. Show the tree after each iteration of your loop condition. You should make reference to the algorithm HeapBottomUp in Appendix D. [3 marks] Determine the computational complexity of HeapBottomUp. Clearly explain all steps in your working. [2 marks] Briefly outline how Heapsort sorts a list of n items in non-decreasing order. [2 marks] You are given a list of one million numbers which are in a random order. How many comparisons would you expect heapsort to take to sort this list? Justify your answer. Activate V [2 marks] to Setting Appendix D: Building a heap ALGORITHM Heap Bottom Up (H[1..n]) //Constructs a heap from elements of a given array // by the bottom-up algorithm //Input: An array H[1..n] of orderable items //Output: A heap H[1..n] for i - [n/2] downto 1 do ki; v heap false H[k] while not heap and 2 * k≤ n do j←2*k if j<n //there are two children if H[j]<H[j+1] j←j+1 if v ≥ H[j] heap ← true else H[k]H[j]; k<j H[k]←v (ai) (b) (c) (d) (e) Let 27, 21, 9, 43, 37, 83, 123, 33 and 97 be the elements of an array A which represents a binary tree T such that for node A[i] in T, the leftson and rightson are A[21] and A[2i + 1] respectively. Draw the binary tree which the array A represents. [2 marks] Convert the tree into a maxheap. Show the tree after each iteration of your loop condition. You should make reference to the algorithm HeapBottomUp in Appendix D. [3 marks] Determine the computational complexity of HeapBottomUp. Clearly explain all steps in your working. [2 marks] Briefly outline how Heapsort sorts a list of n items in non-decreasing order. [2 marks] You are given a list of one million numbers which are in a random order. How many comparisons would you expect heapsort to take to sort this list? Justify your answer. Activate V [2 marks] to Setting Appendix D: Building a heap ALGORITHM Heap Bottom Up (H[1..n]) //Constructs a heap from elements of a given array // by the bottom-up algorithm //Input: An array H[1..n] of orderable items //Output: A heap H[1..n] for i - [n/2] downto 1 do ki; v heap false H[k] while not heap and 2 * k≤ n do j←2*k if j<n //there are two children if H[j]<H[j+1] j←j+1 if v ≥ H[j] heap ← true else H[k]H[j]; k<j H[k]←v

Answer rating: 100% (QA)

i Generally the binary representation looks like this ii we will start checking from 43 because afte... View the full answer