Let A be an integer array and n is the number of elements in the array....
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Let A be an integer array and n is the number of elements in the array. Letj, k and m are arbitrary indexes of array A. Let h be the height of a tree. LEFT(i) means index of left child of node at i. RIGHT (i) means index of right child of node at i. Assume a comparison fails when an index is not set within array bounds or when not set at all. (a) Given an unsorted integer array below and its initial tree representation (The numbers above nodes represent array indexes), Apply the following two procedures, BUILD-TREE and FIX-TREE, to this initial tree to produce a final tree. Show your work by showing intermediate stages of the tree building after each iteration. (15 points) A 14 1 4 2 2 3 4 5 6 7 8 9 10 1 3 2 16 9 10 14 8 7 8 1 10 7 5 16 I 4 9 3 7 10 BUILD-TREE (A, n) for i = FLOOR[n/2] downto 1 do FIX-TREE (A, i, n) FIX-TREE(A, i, n) j=LEFT(i) k = RIGHT(i) if j n and A[j] > A[i] then m = j else m = i if k n and A[k] > A[m] then m = k if m != i then SWAP (A[i], A[m]) FIX-TREE(A, m, n) (b) What is the time comlexity of BUILD-TREE method? (2 points) (c) What is the time comlexity of FIX-TREE method? (3 points) Let A be an integer array and n is the number of elements in the array. Letj, k and m are arbitrary indexes of array A. Let h be the height of a tree. LEFT(i) means index of left child of node at i. RIGHT (i) means index of right child of node at i. Assume a comparison fails when an index is not set within array bounds or when not set at all. (a) Given an unsorted integer array below and its initial tree representation (The numbers above nodes represent array indexes), Apply the following two procedures, BUILD-TREE and FIX-TREE, to this initial tree to produce a final tree. Show your work by showing intermediate stages of the tree building after each iteration. (15 points) A 14 1 4 2 2 3 4 5 6 7 8 9 10 1 3 2 16 9 10 14 8 7 8 1 10 7 5 16 I 4 9 3 7 10 BUILD-TREE (A, n) for i = FLOOR[n/2] downto 1 do FIX-TREE (A, i, n) FIX-TREE(A, i, n) j=LEFT(i) k = RIGHT(i) if j n and A[j] > A[i] then m = j else m = i if k n and A[k] > A[m] then m = k if m != i then SWAP (A[i], A[m]) FIX-TREE(A, m, n) (b) What is the time comlexity of BUILD-TREE method? (2 points) (c) What is the time comlexity of FIX-TREE method? (3 points)
Expert Answer:
Answer rating: 100% (QA)
Solutions Step 1 Given the information in the image and the common practices of heap construction and adjustment lets go through the process step by step The process outlined in your image seems to be ... View the full answer
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date:
Students also viewed these programming questions
-
Under which article does legitimate national law overrule conflicting state laws?
-
How can a company optimize its supply chain operations to minimize costs while ensuring efficient delivery and quality control? Discuss the various strategies, such as lean manufacturing, inventory...
-
The management of Mecca Copy, a photocopying centre located on University Avenue, has compiled the following data to use in preparing its budgeted balance sheet for next year: Ending Balances...
-
Slit 1 of a double slit is wider than slit 2, so that the light from 1 has amplitude 3.00 times that of the light from 2. Show that for this situation, Equation 37.11 is replaced by the equation I =...
-
You are selling your for-profit company and are preparing all the financial documents that would be required by a potential buyer. In this context, which financial statement is the most important?...
-
Define substantive fairness. What factors will a court consider in determining the substantive fairness of a premarital agreement?
-
What are the six security levels? Name at least three specific issues that apply to each level. Also provide three examples of threat categories, attacker profiles, and types of attacks.
-
Use the information below to calculate the machine's depreciation expense Machines initial cost $820 Residual value. $120 The Company started to use the machine on May 1, 2020 The useful fe of the...
-
The 21st Century Studios is about to begin the production of its most important (and most expensive) movie of the year. The movies producer, Dusty Hoffmer, has decided to use PERT/CPM to help plan...
-
941, SUTA and 940 Tax Return Preparation Ingram Heating & Cooling reports the following earnings and deductions for their employees for ...
-
4. Interrupt priority. Suppose that the interrupt sources Timero clear timer on compare match (CTC), external interrupt 1 (INT1), and the transmit complete serial interrupt are enabled. Answer the...
-
The Government of Canada auctioned a new benchmark 2 year bond, to settle on October 2nd, 2020. The bond has a maturity of November 1st, 2022. Assume the bond pays coupons semi-annually and has an...
-
For the block diagram shown below, find the transfer function Y(s) U(s) answer. Step U(s) Answer: Y(s) U(s) Use proper form to represent the transfer function in your 1 S+2 Y(s) Transfer Fcn Scope...
-
(a) The following information on credit and advances are found in the book of Jack and Jane bank: i. Letter of credit GHC40000.00 ii. iii. iv. Mortgage GHC23000.00 Personal loan GHC2400 Bankers'...
-
Part A What is the bubble's diameter just as it reaches the surface of the lake, where the water temperature is 20 C? Assume that the air bubble is always in thermal equilibrium with the surrounding...
-
Sand Dollars Corporation is "the premier roaster, marketer and retailer of specialty coffee in the world, operating in 75 countries" with over 27,000 company-operated and licensed stores worldwide....
-
A non-charmed baryon has strangeness S = 2 and electric charge Q = 0. What are the possible values of its isospin I and of its third component I z ? What is it usually called if I = 1/2?
-
The join operation takes two dynamic sets S 1 and S 2 and an element x such that for any x 1 S 1 and x 2 S 2 , we have x 1 .key x.key x 2 .key. It returns a set S = S 1 {x} S 2 . In this...
-
Suppose that we were to implement B-TREE-SEARCH to use binary search rather than linear search within each node. Show that this change makes the CPU time required O(lg n), independently of how t...
-
Show that for any integer n ? 0, n k = n2"-1 k=0
-
In the Skycoaster amusement park ride, riders are suspended from a tower by a long cable. A second cable then lifts them until they reach the starting position indicated in Figure P5.3. The lifting...
-
Bethany, who weighs 560 N, lies in a hammock suspended by ropes tied to two trees. One rope makes an angle of 45 with the ground; the other makes an angle of 30. Find the tension in each of the ropes.
-
A vendor at the local art fair ties her tent to the concrete-filled coffee can shown in Figure P5.34. A stiff breeze comes up and the string becomes taut. What is the maximum value that the string...
Study smarter with the SolutionInn App