write pseudocode or explain in words please Question 4: l. Say that a pointer p

Question

write pseudocode or explain in words please

Question 4: l. 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 minimu 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,z). 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 - Mar, 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

Solution:

1)

As we have the 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 the first element. this will work in O(logn) as heapify operation take only log n time to heapify heap.

2)

As both heaps have same element so the middle node is going to be same for both heap.The idea is similar to the first algorithm we have to swap node to delete the element. Delete in both 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 max heapify from mid node point.

Please, please upvote and ask your doubts in the comments.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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