Question: We can build a heap by repeatedly calling MAX-HEAP-INSERT to insert the elements into the heap. Consider the following variation on the BUILD-MAX-HEAP procedure: BUILD-MAX-HEAP

We can build a heap by repeatedly calling MAX-HEAP-INSERT to insert the elements into the heap. Consider the following variation on the BUILD-MAX-HEAP procedure:

BUILD-MAX-HEAP′ (A)

1 A.heap-size = 1

2 for i = 2 to A.length

3 MAX-HEAP-INSERT(A, A[i])

a. Do the procedures BUILD-MAX-HEAP and BUILD-MAX-HEAP′ always create the same heap when run on the same input array? Prove that they do, or provide a counterexample.

b. Show that in the worst case, BUILD-MAX-HEAP′ requires Θ(n lg n) time to build an n-element heap.

Step by Step Solution

★★★★★

3.41 Rating (157 Votes )

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock

a The procedures BUILDMAXHEAP and BUILDMAXHEAP do not always cre... View full answer

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Introduction to Algorithms Questions!

The procedure BUILD-MAX-HEAP in Section 6.3 can be implemented by repeatedly using MAX-HEAP-INSERT to insert the elements into the heap. Consider the following implementation: BUILD-MAX-HEAP'(A) 1...

Write a program to take N elements and do the following: a. Insert them into a heap one by one. b. Build a heap in linear time. Compare the running time of both algorithms for sorted,...

a. Prove that for binary heaps, buildHeap does at most 2N2 comparisons between elements. b. Show that a heap of eight elements can be constructed in eight comparisons between heap elements. c. Give...

We can build a heap by repeatedly calling MAX-HEAP-INSERT to insert the elements into the heap. Consider the following variation on the BUILD-MAX-HEAP procedure: BUILD-MAX-HEAP'(A) 1 A.heap-size = 1...

Problem 1 (2 points) Solving Recurrence Relations Draw the recursion tree for T(n) = 3T (Ln/2)) + cn, where c is a constant, and provide a tight asymptotic bound on its solution. Verify your bound...

Problem 3 (4 points) Heapsort (1) (2 points) Show the sorting process on the array A = using Heapsort; (2) (2 points) We can build a heap by repeatedly calling Max-Heap-Insert to insert the elements...

Please do (2) a and b Problem 3 (4 points) Heapsort (1) (2 points) Show the sorting process on the array A = using Heapsort; (2) (2 points) We can build a heap by repeatedly calling Max-Heap-Insert...

Algorithm Problem: Could you please explain how to solve it step by step? Problem 3 (4 points) Heapsort (1) (2 points) Show the sorting process on the array A = using Heapsort; (2) (2 points) We can...

Can you do part (1) with all details needed? Problem 3 (4 points) Heapsort (1) (2 points) Show the sorting process on the array A = using Heapsort; (2) (2 points) We can build a heap by repeatedly...

Algorithm problems, Could you please explain how to solve it? Problem 1 (2 points) Solving Recurrence Relations Draw the recursion tree for T(n) = 3T (Ln/2)) + cn, where c is a constant, and provide...

The director of the art department at an advertising company, Wilson Watson, wants to hire new office staff. His boss tells him that to do so he must find in his budget not only the base salary for...

Why Organizational Behavior is important for the management?

Question 1 : You are considering an investment in Company A . You have examined the projected sales and percentage renurns of Company A as outlined in the table below. \ table [ [ Probability ,...

1.4 describe the process of conducting SEM and explain the various steps involved;

Consider the implementation of CircularlyLinkedList.addFirst, in Code Fragment 3.16. The else body at lines 39 and 40 of that method relies on a locally declared variable, newest. Redesign that...

Isabel has an interesting way of summing up the values in an array A of n integers, where n is a power of two. She creates an array B of half the size of A and sets B[i] = A[2i]+ A[2i+ 1], for i =...

Suppose you are given an array, A, containing n distinct integers that are listed in increasing order. Given a number k, describe a recursive algorithm to find two integers in A that sum to k, if...

A researcher has conducted a study and has obtained a data set. He is seeking your help and requests that you calculate the mean, range, median, and mode and distinguish which of these are measures...

If a bond pays $50 interest semi-annually with a par value of $1,000, its coupon rate is 5% 10% 15% 20% Investors are willing to purchase bonds with a call feature only if the bonds offer a(n)...

Why is growing the number of users such an important metric for social media companies? How does Metcalfes Law relate to the profitability of social media companies? How could LinkedIn help create...