Question

a) Write PSEUDO CODE!!! for Min_Heap_Delete(A,i) which deletes the item at position i in Min_Heap A. Assume that A is a one-dimensional array. Hint:Think about “bubbling up” and “bubbling down” and the operations that do these.

b) give the best upper bound you can on the worst case running time of your method, in ordered notations.

SOLVE IN PSEUDO CODE ONLY!!!! NOT JAVA!!

Answer 1

1.Ans: void MinHeap::deleteKey(int i)

{

    decreaseKey(i, INT_MIN);

    extractMin();

}

int MinHeap::extractMin()

{

    if (heap_size <= 0)

        return INT_MAX;

    if (heap_size == 1)

    {

        heap_size--;

        return harr[0];

    }

    // Store the minimum value, and remove it from heap

    int root = harr[0];

    harr[0] = harr[heap_size-1];

    heap_size--;

    MinHeapify(0);

    return root;

}

2.its takes O(logn) times

I hope this helps you give an upvote!!