The discussion shows our algorithm for building the initial heap in the heapsort algorithm. The algorithm is
Question:
The discussion shows our algorithm for building the initial heap in the heapsort algorithm. The algorithm is reasonably efficient, but we can make it even more efficient. The more efficient algorithm uses a method that creates a heap from a subtree of the complete binary tree. This method has the following specification:
You can write the heapifySubtree method yourself. Using this method, you can make an entire n-element array into a heap with the algorithm:
for (i = (n/2); i > 0; i--)
heapifySubtree(data, i-1, n);
For example, with n = 10, we will end up making the following sequence of activations:
heapifySubtree(data, 4, 10);
heapifySubtree(data, 3, 10);
heapifySubtree(data, 2, 10);
heapifySubtree(data, 1, 10);
heapifySubtree(data, 0, 10);
It turns out that this method is actually O(n) rather than O(n log n).
For this project, reimplement makeHeap, as outlined above.
private static void heapifySubtree( int[ ] data, int root0fSubtree, int n // Precondition: data is an array with at least // n elements, and rootOfSubtree < n. We will // consider data to represent a complete // binary tree, and in this representation the // node at data[rootOfSubtree] is the root of // a subtree called s. This subtree s is already // a heap, except that its root might be out of // place. // Postcondition: The subtree s has been // rearranged so that it is now a valid heap.
Step by Step Answer:
Here is an implementation of the heapifySubtree method in Java public void heapifySu...View the full answer
Students also viewed these Computer science questions
-
The R&D division of Simplex Chemical Corp. has just developed a chemical to sterilize the voracious mountain pine beetles that are invading Western Canada's forests. The president of Simplex is...
-
You are given a full complete binary tree T of height d (Figure 1). In such a tree the d-th layer consists of 24-1 leaves, and each of the vertices in the first (d 1) layers has exactly 2 children....
-
A compare-exchange operation on two array elements A[i] and A[j], where i < j, has the form COMPARE-EXCHANGE (A, i, j) 1 If A[i] > A[j] 2 exchange A[i] with A[j] After the compare-exchange operation,...
-
Assume that when human resource managers are randomly selected, 57% say job applicants should follow up within two weeks. If 9 human resource managers are randomly selected, find the probability that...
-
Refer to the TEMPAGE column in Data Set 18 in Appendix B, and construct a frequency table of the ages of patients admitted for voluntary surgery. Start at age 13 and use a class width of 17.5. Does...
-
Modify the AnimationinJavaFX application created in the You Do It exercise to add a triangle and have it follow a path. Also, have the object change colors from yellow to green. Save the project as...
-
For the original 4340 steel-reinforced concrete post design of Problem 1.13 and the new IM9 carbon fiber-reinforced concrete post design of Problem 1.16, compare the tensile stress-to-tensile...
-
At the time of his death this year on September 4, Kenneth owned the following assets. Fair Market Value City of Boston bonds $2,500,000 Stock in Brown Corporation 900,000 Promissory note issued by...
-
1. Identifies the barriers to communication experienced in this scenario as well as their impact. 2. What are the communications barriers that Barry faces? 3. What solutions might Barry consider to...
-
An investment analyst collects data on stocks and notes whether or not dividends were paid and whether or not the stocks increased in price over a given period. Data are presented in the following...
-
Rewrite quicksort so that there are no recursive calls. The technique is to use a stack to keep track of which portions of the array still need to be sorted. Whenever we identify a portion of the...
-
On problem with mergesort is that it constantly needs a new temporary array. One solution to the problem is to rewrite the mergesort according to the following specification: void mergesort( int...
-
Determine whether the set of rational numbers under the operation of multiplication forms a group. Explain your answer.
-
A program is to read a numeric score (0 to 100) and display an appropriate letter grade (A, B, C, D, or F). 1. What is the functional domain of this program? 2. Is exhaustive data coverage possible...
-
The C++ thread library provides a function that returns the number of threads that the hardware is capable of running. Modify the parallel merge sort so that the user specifies a minimum chunk size....
-
Write a queue application that determines if two files are the same.
-
Why is it good practice to put a class declaration in one file and the implementation in another?
-
Differentiate between top-down and bottom-up integration testing.
-
After being downsized by his former employer, in November 2015, Wayne moves from Minnesota to Alabama to accept a new job. When filing his Federal income tax return for 2015, Wayne deducts the...
-
Recall that Chapter 8 described the binary search algorithm for finding a particular entry in an ordered list. The idea behind binary search is to begin looking in the exact center of the list. If...
-
Section 3.3 presents basic operation and possible implementations of multipliers. A basic unit of such implementations is a shift - and-add unit. Show a Verilog implementation for this unit. Show how...
-
Repeat Exercise B.22, but for an unsigned divider rather than a multiplier. Data from in Repeat Exercise B.22 Section 3.3 presents basic operation and possible implementations of multipliers. A basic...
-
The ALU supported set on less than (slt) using just the sign bit of the adder. Lets try a set on less than operation using the values -7 ten and 6 ten . To make it simpler to follow the example, lets...
-
You are planning to retire in 30 years. You want to be able to spend $40,000 per year in retirement, adjusted for inflation (so you will spend the equivalent in each year of $40,000 in today's...
-
From a lawsuit, you have been awarded a 31-payment, constant growth annuity. The first payment is at Year O and is equal to $380, and each subsequent payment will be paid in 16 month intervals, with...
-
You will receive 13 payments of $535, where the first payment will be received today (Month 0) and all other payments will be received in 10-month intervals (Months 10, 20, 30 ... 120). Assume that...
Study smarter with the SolutionInn App