As discussed in class, one way to remove an object from a heap is to decrease it

Question

As discussed in class, one way to remove an object from a heap is to decrease its priority value to negative infinity, percolate it up to the root of the heap, and then call deleteMinQ. An alternative is to simply remove it from the heap, thus creating a hole, and then repair the heap. Write pseudocode for an algorithm that will perform the remove operation according to the alternative approach described above. Your pseudocode should implement the method call remove(int index), where index is the index into the heap array for the object to be removed. Your pseudocode can make calls to the following methods described in lecture: insertQ, deleteMinQ, percolateUp(), and percolateDown(). Like in lecture, you may assume that objects are just integer priority values (we will ignore the data associated with the priorities). What is the worst case complexity of the algorithm you wrote in part (a)?

Explanation / Answer

worst case complexity = O(nlogn)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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