General Doubt

Question

Suppose i delete the root element from the heap then i will apply the heapify() procedure on root,and suppose if i delete a random element form heap which will take O(n) time in total then the procedure is:-

1. Locate the element.

2.Swap with the last element

3.Delete the last element and perform Heapify() again.But this  heapify() we need to apply on root or the swapped location ?

And During insertion of particular element we need to do:-

1. Insert and element in the last node according to level order traversal then:-

                for(i = n/2 downto 1){ Maxheapify(A[i]) }

Am i right?

And following this strategy we will find the minimum number of swaps or comparison required isnt it?

Comments

Please provide some thought here :)

Answer 1

IN worst case deletion from heap will take O (logn)..if u want to delete random element from heap...so to find that element it will take O (n) time...and just delete that element...replace with last element to maintain the property of heap ACBT (almost complete binary tree)...now after replaceming u cant perform either minheapify Top or Minheapify Bottom....beacuse u dont know which side to Go to arrange the tree(Up Or Down)....so just apply Min heapify Top from root to maintain heap property.