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:
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%.
-
Set up an image system to compute the flow of a source at unequal distances from two walls, as shown in Fig. P8.73 Find the point of maximum velocity on the y-axis. rm 2a
-
Apply Dijkstra's algorithm to the weighted directed multigraph shown in Fig. 13.33, and find the shortest distance from vertex a to the other seven vertices in the graph. 15 4 14 Figure 13.33
-
A two-stroke I.C. engine has (a) inlet and exhaust valves (b) inlet and exhaust ports (c) inlet, exhaust and transfer ports (d) only transfer ports
-
FFDP Corp. has yearly sales of $28 million and costs of $12 million. The companys balance sheet shows debt of $54 million and cash of $18 million. There are 950,000 shares outstanding and the...
-
What role does non-Fourier heat conduction play in microscale and nanoscale heat transfer, and how do theories like the Cattaneo-Vernotte model or the dual-phase-lag model address these non-classical...
-
Match correct purposes, contents, and users regarding SOC reports. Purposes/Contents/Users a. Easy to read by the general public in a summary format on security, availability, processing integrity,...
-
Overhead costs will be assigned to procedures, based on the amountoperating room hours. Reithofer Medical Center expects to use eight operating theaters on averagehours per day, seven days per week....
-
Flood control and management are critical aspects of civil engineering, particularly in regions prone to flooding due to factors such as heavy rainfall, river overflow, storm surges, and inadequate...
-
You have a friend who knows that you are studying Psychology in university. In a conversation you mention that you are doing a course on the History and Philosophy of Psychology. The friend tells you...
-
Assuming no friction, if a falling ball arrives at the floor with kinetic energy of 350 J, what is its elastic potential energy when the ball comes to a complete stop?
-
Discuss the concept of order cycle time in logistics management.
-
How does digital marketing influence and reshape traditional marketing communication channels?
-
The 2025 Annual Report of Blue International contains the following information: (in millions) Total assets Total liabilities Net sales Net income (a) (b) June 29, 2025 (c) $1,481 964 2,762 127 June...
-
Find the center of mass of a thin triangular plate bounded by the y-axis and the lines y = x and y = 2 - x if (x, y) = 6x + 3y + 3.
-
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.
-
Fluid is a substance that: (a) Cannot be subjected to shear force (b) Always expands until it fills any container (c) Has the same shear stress at a point regardless of its motion (d) Cannot remain...
-
Sketch and explain split air conditioner?
-
Define air conditioning. State the basic component of air conditioning systems.
Study smarter with the SolutionInn App