Concept explainers
(a)
To show the difference between the output of the array when it is passed as an array for BUILD-MAX-HEAP and BUILD-MAX-HEAP'.
(a)
Explanation of Solution
Given Information: A heap that has n-elements.
Explanation:
Pseudo code for BUILD-MAX-HEAP is given below:
| BUILD-MAX-HEAP( A ) |
| A.heapsize = A.length |
| for i = A.length/2 downto 1 |
| MAX-HEAPIFY( A,i ) |
Consider an array A= {1, 2, 3, 4, 5, 6}. If the above
The for-loop will iterate from 3 to 1.
At i=3 , MAX-HEAPIFY will be called with arguments as array A and i=3 . The following pseudo code for MAX-HEAPIFY is as follows:
| MAX-HEAPIFY( A,i ) |
| l = LEFT( i ) |
| r = RIGHT( i ) |
| ifl <= A.heapsize and A[l]> A[i] |
| largest = l |
| Else |
| largest = i |
| ifr <= A.heapsize and A[r]> A[largest] |
| largest=r |
| iflargest != i |
| exchange A [ i ] with A [ largest ] |
| MAX-HEAPIFY( A,largest ) |
Currently at i=3 , A [3]=3 and have the following tree:
At the end of the iteration:
At i=2 , A [2]=2 and after executing the algorithm, the following tree is evolved:
At i=1 , A [1]=1 and after executing the algorithm, the following tree is evolved:
Resultant array after BUILD-MAX-HEAP is A= {6, 5, 3, 4, 2, 1}
However, according to the question, the algorithm for BUILD-MAX-HEAP ', there is an alteration in A.heapsize, which is by default 1. Moreover, the value of i starts from 2 and goes on till A.length that is 6.
At i=2 , A [2]=2. The tree is given below-
Look at the algorithm of BUILD-MAX-HEAP' . It is using MAX-HEAP-INSERT. So, it becomes-
At i=3 , A [3]=3 and after using MAX-HEAP-INSERT
At i=4 , A [4]=4 and after using MAX-HEAP-INSERT
At i=5 , A [5]=5 and after using MAX-HEAP-INSERT
Finally at i=6,A [6]=6 and after using MAX-HEAP-INSERT
Resultant array after BUILD-MAX-HEAP' is A= {6, 4, 5, 1, 3, 2}
Hence, the resultant array after BUILD-MAX-HEAP and BUILD-MAX-HEAP' is not the same.
(b)
To determine the worst case scenario for BUILD-MAX-HEAP' while entering n-elements.
(b)
Explanation of Solution
The BUILD-MAX-HEAP' has MAX-HEAP-INSERT in it, which has worst case of Θ(log n). The call to this function is done for n-1 times, since it is not considering the parent node here.
The worst case for MAX-HEAP-INSERT happens when an array is sorted in ascending order.
Each insert step takes maximum Θ(log n ) steps, and since it is done for n times, it takes a worst case of Θ(nlog n ). Each iteration in the new block is actually taking more time as the older version as it has more iteration in it. The new block will work in even work in even worse case as it has the usage of other algorithm as well.
Want to see more full solutions like this?
Chapter 6 Solutions
Introduction To Algorithms, Third Edition (international Edition)
- (use R language)Scatter plot(a). Run the R code example, and look at the help file for plot() function. Try different values for arguments:type, pch, lty, lwd, col(b). Use par(mfrow=c(3,2)) and output 6 plots with different argument settings.arrow_forward1. Draw flow charts for each of the following;a) A system that reads three numbers and prints the value of the largest number.b) A system reads an employee name (NAME), overtime hours worked (OVERTIME), hours absent(ABSENT) and determines the bonus payment (PAYMENT).arrow_forwardScenario You work for a small company that exports artisan chocolate. Although you measure your products in kilograms, you often get orders in both pounds and ounces. You have decided that rather than have to look up conversions all the time, you could use Python code to take inputs to make conversions between the different units of measurement. You will write three blocks of code. The first will convert kilograms to pounds and ounces. The second will convert pounds to kilograms and ounces. The third will convert ounces to kilograms and pounds. The conversions are as follows: 1 kilogram = 35.274 ounces 1 kilogram = 2.20462 pounds 1 pound = 0.453592 kilograms 1 pound = 16 ounces 1 ounce = 0.0283 kilograms 1 ounce = 0.0625 pounds For the purposes of this activity the template for a function has been provided. You have not yet covered functions in the course, but they are a way of reusing code. Like a Python script, a function can have zero or more parameters. In the code window you…arrow_forward
- make a screen capture showing the StegExpose resultsarrow_forwardWhich of the following is not one of the recommended criteria for strategic objectives? Multiple Choice a) realistic b) appropriate c) sustainable d) measurablearrow_forwardManagement innovations such as total quality, benchmarking, and business process reengineering always lead to sustainable competitive advantage because everyone else is doing them. a) True b) Falsearrow_forward
- Vision statements are more specific than strategic objectives. a) True b) Falsearrow_forwardThe three components of the __________ approach to corporate accounting include financial, environmental, and social performance measures. Multiple Choice a) stakeholder b) triple dimension c) triple bottom line d) triple efficiencyarrow_forwardCompetitors, as internal stakeholders, should be included in the stakeholder management consideration of a company and in its mission statement. a) True b) Falsearrow_forward
- At what level in the organization should the strategic management perspective be emphasized? Multiple Choice a) throughout the organization b) from the bottom up in an organization c) at the top of the organization d) at the middle of the organizationarrow_forwardA good manager can be flexible when it comes to sticking to the original plan; to get good results, the intended strategy has to become the realized strategy. a) True b) Falsearrow_forward________ tend to be quite enduring and seldom change. Multiple Choice a) Strategic objectives b) Vision statements c) Strategic plans d) Mission statementsarrow_forward
C++ Programming: From Problem Analysis to Program...Computer ScienceISBN:9781337102087Author:D. S. MalikPublisher:Cengage Learning
Systems ArchitectureComputer ScienceISBN:9781305080195Author:Stephen D. BurdPublisher:Cengage Learning
C++ for Engineers and ScientistsComputer ScienceISBN:9781133187844Author:Bronson, Gary J.Publisher:Course Technology Ptr
Programming Logic & Design ComprehensiveComputer ScienceISBN:9781337669405Author:FARRELLPublisher:Cengage
New Perspectives on HTML5, CSS3, and JavaScriptComputer ScienceISBN:9781305503922Author:Patrick M. CareyPublisher:Cengage Learning
Operations Research : Applications and AlgorithmsComputer ScienceISBN:9780534380588Author:Wayne L. WinstonPublisher:Brooks Cole