1. 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?
2. If a d-heap is stored as an array, for an entry located in position i, where are the parents and children?