This is a question with multiple parts and is not two questions posted in one. Q

Question

This is a question with multiple parts and is not two questions posted in one.

Question 4:
1. Say that a pointer p points to an element in the middle of a heap. Give an O(log n)
time algorithm to remove this element from the heap. Hint: Its very similar to
regular delete.

2. Say that we want to maintain two Heaps one with the minimum at the top (and
the children no smaller than the parent) and one with the maximum on the top
(and the children no larger than the parent). Thus the operations we want to
maintain are Delete Max(H), Delete Min(H) and Insert(H, x). Use two
heaps with pointers between two copies of the same elements so that the above
operations could be done in O(log n) each. Note that Delete Max, also deletes
this item from the Min Heap. Further, this element can be located in the
middle of the Min Heap.

Hint: Use part 1 that explains how to delete a vertex from the middle of a Heap.

Explanation / Answer

1. As we have pointer to middle node We can swap this node with the rightest leaf node in heap and we will heapify the heap from mid node to first element. this will work in O(logn) as heapify operation take only log n time to heapify heap.

2.As both heap have same element so middle node is going to be same for both heap.The idea is similar to first algorithm we have to swap node to delete the element . Delete in noth Min and Max as in both heap element is middle one only So in both mid element is swap with last node and delete the last node in O(1) time by decreasing size of heap and min heap is going to be min heapify and max heap going to be max heapify from mid node point.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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