# Question

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 heap-size [A] ← 1

2 for i ← 2 to length [A]

3 do 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.

BUILD-MAX-HEAP'(A)

1 heap-size [A] ← 1

2 for i ← 2 to length [A]

3 do 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.

## Answer to relevant Questions

A d-ary heap is like a binary heap, but (with one possible exception) non-leaf nodes have d children instead of 2 children. a. How would you represent a d-ary heap in an array? b. What is the height of a d-ary heap of n ...Given a set of n numbers, we wish to find the i largest in sorted order using a comparison based algorithm. Find the algorithm that implements each of the following methods with the best asymptotic worst-case running time, ...Suppose that we wish to keep track of a point of maximum overlap in a set of intervals—a point that has the largest number of intervals in the database overlapping it.a. Show that there will always be a point of maximum ...In the depth-determination problem, we maintain a forest F = (Ti) of rooted trees under three operations:• MAKE-TREE (v) creates a tree whose only node is v.• FIND-DEPTH (v) returns the depth of node v within its ...Give a dynamic-programming solution to the 0–1 knapsack problem that runs in O (n W) time, where n is number of items and W is the maximum weight of items that the thief can put in his knapsack.Post your question

0