Question

One way to remove an object from a binary min heap is to decrease its priority value by 1 and then call deleteMin. An alternative is to remove it from the heap, thus creating a hole, and then repair the heap.

Write pseudocode for an algorithm that performs the remove operation using 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 call the following methods described in lecture: insert, deleteMin, percolateUp, and percolateDown. Like in lecture, you may assume that objects are just priority integers (no other data).

What is the worst-case complexity of the algorithm you wrote?

Answer 1

Pseudocode for Remove operation in heap (min-heap) :

• 1. Find the index i of the object in the heap array that we want to delete. This i is given in the argument of the Remove(int index) method.
• 2. Swap this object at index i with the last object of the heap array at the nth index. [ Swapping will fill in the hole created on deleting the required object in the heap, and make it a complete binary tree again but not necessarily a heap now ]
• 3. Call percolateUp() or percolateDown() method to fix the heap property and make this complete binary tree back to a heap
• if( object (i) < parent(i) ) call percolateUp()
• else call percolateDown()

Time Analysis of Remove operation in heap :

• Running time of Remove(int index) in a heap of n objects = height of the heap tree
• = O(log n) in the worst-case
• The worst-case time complexity of the above algorithm depends upon the height of the heap tree because we are using percolate up/down methods which is O(logn) and the rest of the operations like swaps and comparisons will take constant time only.

Feel free to ask any doubt you may have. Happy to help.