Each deleteMin operation uses 2 log N comparisons in the worst case. ?a. Propose

Question

Each deleteMin operation uses 2 log N comparisons in the worst case. ?a. Propose a scheme so that the deleteMin operation uses only log N + log log N + O(1) comparisons between elements. This need not imply less data movement. ?? b. Extend your scheme in part (a) so that only log N + log log log N + O(1) comparisons are performed. ??c. How far can you take this idea? d. Do the savings in comparisons compensate for the increased complexity of your algorithm? Below is example of one deleteMin method in binary heap from the book :

Thank you.

Explanation / Answer

Solution:

if the heap we considered organized as min heap then we start the whole from root, find the path down to a leaf by taking the minimum child. This requires roughly logN comparisons. To find the correct place where to move the hole, perform a binary search on the logN elements. This takes O(log log N) comparisons.

Solution:

First find the path of minimum children , stopping after log N - log log N levels. At this point, it is easy to determine if the hole should be placed above or below the stopping point. If it goes below, then continue finding the path, but perform the binary search on only the last loglogN elements on the path, for a total of logN + log log log N comparisons. Otherwise, perform a binary search on the first log N - log log N elements. The binary search takes at most log log N comparisons, and the path finding took only log N - log log N, so the total in this case is log N. So the worst case is the first case.

Solution:

It depends on the elements size to consider how far we can continue the process

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.