Answered You can hire a professional tutor to get the answer.

QUESTION

In what follows A is an array representing a binary heap that contains N distinct keys where N is a power of 2; we call the heap in A the main heap.

In what follows A is an array representing a binary heap that contains N distinct keys where N is a power of 2; we call the heap in A the main heap. A much smaller second array a is large enough to contain a binary heap of only n keys, where n ≤ log N; we call the heap in a the auxiliary heap. The auxiliary heap is initially empty. In what follows, whenever we say "insert in the auxiliary heap a key x from the main heap", we implicitly imply storing, alongside every such x, its position in the main heap (i.e., its position in array A). None of what is described below causes any modification to the main heap: It only reads information from the main heap, all the modifications described occur in the auxiliary heap. • Insert, in the auxiliary heap, the key at the root of the main heap. • Repeat n − 1 times the following: - Do a remove-max operation on the auxiliary heap, say it returns the key at node v of the main heap. - Insert, in the auxiliary heap, the keys of the two children of v in the main heap. • Return the maximum element in the auxiliary heap. 

6.The key returned by the last step of the above algorithm is (choose the best answer) 1. A key whose depth in the main heap is between n/2 and n 2. A key whose depth in the main heap is n 3. The kth largest key in the main heap, where k is between n/2 and n 4. The nth largest key in the main heap 5. A key that need not satisfy any of the above four choices 

7.The time taken by the above algorithm depends on n, not on N. It is closest to being (choose the best answer) 1. O(n) 2. O(n log(log n)) 3. O(n log n) 4. O(n(log n) 2 ) 5. O(n 2 )

Show more
LEARN MORE EFFECTIVELY AND GET BETTER GRADES!
Ask a Question