Deletetion in heaps

#1

I have wriiten 2 downHeapify functions, but number 2 didnot work number 1 did,
i wanna know why , because we know that which ever in greater should be swaped and then we should call further, i did not understand why that didnot work, please explain.

#2

actually both of your downheapify functions are incorrect.

  1. downheapify() function is logically incorrect.
    as we compare root, its left value, and its right value to decide which will come to top.
    if (pq[c1] > pq[root] && pq.size() > c1)
    {
    final = c1;
    }
    if (pq[c2] > pq[root] && pq.size() > c2)
    {
    final = c2;
    } is incorrect implementation for deciding largest of three.

correct solution:
final = root;
if ( pq.size() > c1 && pq[c1] > pq[root])
{
final = c1;
}
if ( pq.size() > c2 && pq[c2] > pq[final])
{
final = c2;
}
notice that I place [ c1<pq.size() ] condition first. this is imp as you should access pq[c1] only after checking that condition otherwise run time error can occur.

  1. downheapify2() : this function has no logical error. the only problem is what i mentioned in the last of downheapify(). i.e. place [ c1<pq.size() ] condition first.
    this function will work but its time complexity is O(n) as you are exploring both the child.
    while the time complexity of downheapify() is O(logn)

final best solution is: https://ide.codingblocks.com/s/214456

thanks
please rate and resolve if satisfied.

1 Like
#3

Thnks, i understood the problem