Given an array out of order, HeapSort() sorts it by using a max-heap. Check out the...
Fantastic news! We've Found the answer you've been seeking!
Question:
![Given an array out of order, HeapSort() sorts it by using a max-heap. Check out the following algorithm.](https://dsd5zvtm8ll6.cloudfront.net/si.experts.images/answers/2023/10/6523c42826dee_7926523c42821f17.jpg)
Transcribed Image Text:
Given an array out of order, HeapSort() sorts it by using a max-heap. Check out the following algorithm. HeapSort (A) BUILD-MAX-HEAP (A) for i = A.length down to 2 Exchange A[1] with A[i] A.heap_size = A.heap_size -1 MAX-HEAPIFY (A, 1) // Line X For example, an out-of-order array A = [4.1.3.2.16,9,10,14,8.,7] will become [16, 14, 10, 8, 7, 9, 3, 2, 4, 1] after BUILD-MAX-HEAP (A) Then for each iteration of the loop in HeapSort(A), the array A will become [14., 8, 10, 4, 7, 9, 3, 2, 1, 16] [10, 8, 9, 4, 7, 1, 3, 2, 14, 16] [9, 8, 3, 4, 7, 1. 2. 10, 14, 16) [8, 7, 3, 4, 2, 1, 9, 10, 14, 16] [7, 4, 3, 1, 2, 8, 9, 10, 14, 16] [4, 2, 3,1, 7, 8, 9, 10, 14, 16] [3. 2, 1, 4, 7, 8, 9, 10, 14, 16] [2.1, 3, 4,7, 8, 9, 10, 14, 16] [1, 2, 3, 4, 7, 8, 9, 10, 14, 16] Suppose A = [5, 3, 17, 10, 84, 19, 6, 22, 9]. (a) Show how A will change after BUILD-MAX-HEAP (A) (b) Show how A will change for each iteration of the loop in Heap Sort(A) Given an array out of order, HeapSort() sorts it by using a max-heap. Check out the following algorithm. HeapSort (A) BUILD-MAX-HEAP (A) for i = A.length down to 2 Exchange A[1] with A[i] A.heap_size = A.heap_size -1 MAX-HEAPIFY (A, 1) // Line X For example, an out-of-order array A = [4.1.3.2.16,9,10,14,8.,7] will become [16, 14, 10, 8, 7, 9, 3, 2, 4, 11 after BUILD-MAX-HEAP (A) Then for each iteration of the loop in HeapSort(A), the array A will become [14, 8, 10, 4, 7, 9, 3, 2, 1, 16] [10. 8. 9. 4, 7, 1, 3, 2, 14, 16] [9, 8, 3, 4, 7, 1. 2. 10, 14, 16] [8, 7, 3, 4, 2, 1. 9, 10, 14, 16] [7. 4, 3, 1,2, 8, 9, 10, 14, 16] [4. 2, 3, 1,7, 8, 9, 10, 14, 16] [3, 2, 1, 4, 7, 8, 9, 10, 14, 16] [2. 1, 3, 4, 7, 8, 9, 10, 14, 16] [1, 2, 3, 4,7, 8, 9, 10, 14, 16] Suppose A = [5, 3, 17, 10, 84, 19, 6, 22, 9]. (a) Show how A will change after BUILD-MAX-HEAP (A) (b) Show how A will change for each iteration of the loop in Heap Sort(A) Given an array out of order, HeapSort() sorts it by using a max-heap. Check out the following algorithm. HeapSort (A) BUILD-MAX-HEAP (A) for i = A.length down to 2 Exchange A[1] with A[i] A.heap_size = A.heap_size -1 MAX-HEAPIFY (A, 1) // Line X For example, an out-of-order array A = [4.1.3.2.16,9,10,14,8.,7] will become [16, 14, 10, 8, 7, 9, 3, 2, 4, 1] after BUILD-MAX-HEAP (A) Then for each iteration of the loop in HeapSort(A), the array A will become [14., 8, 10, 4, 7, 9, 3, 2, 1, 16] [10, 8, 9, 4, 7, 1, 3, 2, 14, 16] [9, 8, 3, 4, 7, 1. 2. 10, 14, 16) [8, 7, 3, 4, 2, 1, 9, 10, 14, 16] [7, 4, 3, 1, 2, 8, 9, 10, 14, 16] [4, 2, 3,1, 7, 8, 9, 10, 14, 16] [3. 2, 1, 4, 7, 8, 9, 10, 14, 16] [2.1, 3, 4,7, 8, 9, 10, 14, 16] [1, 2, 3, 4, 7, 8, 9, 10, 14, 16] Suppose A = [5, 3, 17, 10, 84, 19, 6, 22, 9]. (a) Show how A will change after BUILD-MAX-HEAP (A) (b) Show how A will change for each iteration of the loop in Heap Sort(A) Given an array out of order, HeapSort() sorts it by using a max-heap. Check out the following algorithm. HeapSort (A) BUILD-MAX-HEAP (A) for i = A.length down to 2 Exchange A[1] with A[i] A.heap_size = A.heap_size -1 MAX-HEAPIFY (A, 1) // Line X For example, an out-of-order array A = [4.1.3.2.16,9,10,14,8.,7] will become [16, 14, 10, 8, 7, 9, 3, 2, 4, 11 after BUILD-MAX-HEAP (A) Then for each iteration of the loop in HeapSort(A), the array A will become [14, 8, 10, 4, 7, 9, 3, 2, 1, 16] [10. 8. 9. 4, 7, 1, 3, 2, 14, 16] [9, 8, 3, 4, 7, 1. 2. 10, 14, 16] [8, 7, 3, 4, 2, 1. 9, 10, 14, 16] [7. 4, 3, 1,2, 8, 9, 10, 14, 16] [4. 2, 3, 1,7, 8, 9, 10, 14, 16] [3, 2, 1, 4, 7, 8, 9, 10, 14, 16] [2. 1, 3, 4, 7, 8, 9, 10, 14, 16] [1, 2, 3, 4,7, 8, 9, 10, 14, 16] Suppose A = [5, 3, 17, 10, 84, 19, 6, 22, 9]. (a) Show how A will change after BUILD-MAX-HEAP (A) (b) Show how A will change for each iteration of the loop in Heap Sort(A)
Expert Answer:
Answer rating: 100% (QA)
lets go through the steps for both BUILDMAXHEAP and each iteration of the loop in HeapSort for the a... 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
-
Three stage lights are mounted on a pipe as shown. The lights at A and B each weigh 4.1 lb, while the one at C weighs 3.5 lb. (a) If d = 25 in., determine the distance from D to the line of action of...
-
Give the worst-case Big O running time of this code and explain in detail how you arrived at this answer. for(int j = 0; j < numItems; j++) { int i = numItems; while (i > 0) = i i 3; // integer...
-
A 60 dislocation with a line direction and Burgers vector b in a cubic crystal is shown below. The crystal is subject to hydrostatic pressure p. dislocation line (i) Use the Peach-Koehler formula to...
-
Determine the real roots of (x) = - 1 + 5.5x 4x2 + 0.5x3: (a) Graphically and (b) Using the Newton-Raphson method to within s = 0.01%.
-
Texas Roadhouse opened a new restaurant in October. During its first three months of operation, the restaurant sold gift cards in various amounts totaling $2,500. The cards are redeemable for meals...
-
At what angle will the second-order maximum be seen from a diffraction grating of spacing 1.25 m when illuminated by light of wavelength 550 nm?
-
A product research organization recently published the results of mileage tests of several brands of tires. Five tires of each brand were tested and the mileage results of two of the brands were as...
-
1. Describe the various services provided by logistics service providers. What is the role of these services in focal firms value-chain activities? 2. Supply-chain management has evolved over time,...
-
Thank You! Questions below 2) Suppose youwere hired to estimate replacing the shingles on a sloping roof (shaped like an upside-down "V"). You have some long sticks and a tape measure, but no ladder....
-
The focus of this project is to create a master budget for the Williams Company based on the companys industry outlook, recent company outcomes, and the companys business rules. You will create a...
-
please help!! Pacific Packaging's ROE last year was only \( 2 \% \), but its management has developed a new operating plan that cails for a debt-to-capital ratio of 603 , which Wil result in annual...
-
What are the arguments to support the inclusion of all, fixed and variable, aging costs as product cost? What are the problems? Question 1 In Exhibit 2, is the accounting treatment of "Other costs...
-
Perfect Pet Food, Inc., is a premier manufacturer of both canned and dry food for cats and dogs of all ages and breeds.Located in Kansas City, Kansas, the firm has recently expanded its service area...
-
Stephen runs a pet salon. He is currently grooming 115 dogs per week. If instead of grooming 115 dogs, he grooms 116 dogs, he will add $65.93 to his costs and $69.68 to his revenues. What will be the...
-
Q2. Suppose that time series {X} is an AR(1) process Xt = axt-1 Wt, where 0 < a <1 and W is normalized standard white noise with Wt ~ N(0, 1). If we have observed X1 and X3, and we would like to...
-
The current euro/US dollar exchange rate is 1:$2.Company a Eurozone company, makes a $1,000 sale to a US customer on credit. By the time the customer pays, the euro has strengthened by 20%. What will...
-
On an international scale, tax authorities and international organizations increasingly scrutinize and penalize multinational corporations for misusing transfer pricing. In light of this statement,...
-
Show that the block upper triangular matrix A in Example 5 is invertible if and only if both A 11 and A 22 are invertible. Data from in Example 5 EXAMPLE 5 A matrix of the form A = [ A11 A12 0 A22 is...
-
Show that the class P, viewed as a set of languages, is closed under union, intersection, concatenation, complement, and Kleene star. That is, if L 1 , L 2 P, then L 1 L 2 P, L 1 L 2 P, L 1 L 2 ...
-
Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on the array A = ?31, 41, 59, 26, 41, 58?. Figure 2.2 4 5 6 1 2 3 4 5 6 4 6 1 1 2 3 4 5 6 1 2 3 (a) 2 4 6. 1 3 (b) 2 |5 3 (c) 2...
-
Prove that we can also express the total cost of a tree for a code as the sum, over all internal nodes, of the combined frequencies of the two children of the node.
-
Fitch and Wall have been in partnership for many years sharing profits and losses in the ratio 5 : 3 respectively. The following was their balance sheet as at 31 December 2002. On 1 January 2003,...
-
The Unilever 2002 annual review stated: Total Shareholder Return (TSR) is a concept used to compare the performance of different companies stocks and shares over time. It combines share price...
-
On the Internet find the 2010 Transparency International Corruption Perception Index and determine the ranking of these countries. a. United States b. Japan c. Chad d. Iceland e. Denmark
![Mobile App Logo](https://dsd5zvtm8ll6.cloudfront.net/includes/images/mobile/finalLogo.png)
Study smarter with the SolutionInn App