Design an efficient algorithm for finding and deleting an el

Design an efficient algorithm for finding and deleting an element of the smallest value in a max-heap A[1..n] where n greaterthanorequalto 1. What is the running time of your algorithm?

Solution

Min element in a max heap are in the leaves node which are stored from n/2 onwards in an array.

Reson for it being a leaf node is because a parent needs to be larger than both its children (max heap property).

Algorith,/Pseudocode

This will take O(n) for the search of the minimum element, then O(1) for the switch, and finally O(log n) for the upheap. In total this is linear time, essentially the best you can do.

Remember to be careful with the the index operations, 2*i is the left child of node i and 2*i+1 is the right child of node i in an array based heap (assuming 0th element of the array is always empty and the root of the heap is at index 1)