Answer Happy

Posted: **Fri Jul 08, 2022 6:15 am**

: A I Let 12 37 7 73 146 148 231 72 25 Be The Elements Of An Array A Which Represents A Binary Tree T Such Tha 1 (28.19 KiB) Viewed 34 times

(a) (i) Let 12, 37, 7, 73, 146, 148, 231, 72, 25 be the elements of an array A which represents a binary tree T such that for node A in T, the leftson and rightson are A[21] and A[2i+1] respectively. Draw the binary tree which the array A represents. (ii) 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 F. (iii) Briefly outline how Heapsort sorts a list of n items in non-decreasing order. (iv) You are given a list of one million numbers which are in a random order. You are required to return a sorted list. Which sorting algorithm would you use? Justify you choice.
Appendix F: Building a heap ALGORITHM Heap BottomUp (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]; kj H[k] v ←